Bài Toán Balo 0-1 (Knapsack 1D Rolling Array)

Buổi 22 — DP 2D & LIS Dynamic Programming dynamic-programming
Points
30
AC Rate
40.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Có N đồ vật, vật thứ i có trọng lượng w[i] và giá trị v[i]. Bạn mang một chiếc balo có sức chứa tối đa W. Mỗi đồ vật chỉ được chọn tối đa 1 lần. Hãy tìm tổng giá trị lớn nhất có thể lấy được sao cho tổng trọng lượng không vượt quá W.

Dữ liệu vào (Input)
  • Dòng 1: Hai số nguyên dương N và W (1 ≤ N ≤ 1000, 1 ≤ W ≤ 10^4).
  • N dòng tiếp theo: Mỗi dòng gồm hai số nguyên w[i] và v[i] (1 ≤ w[i] ≤ W, 1 ≤ v[i] ≤ 10^9).
Dữ liệu ra (Output)
  • In ra một số nguyên duy nhất là tổng giá trị lớn nhất đạt được.
Ví dụ mẫu
Sample Input 1
3 8
3 30
4 50
5 60
Sample Output 1
90
Draft saved