Bài Toán Balo 0-1 (Knapsack 1D Rolling Array)
Points
30
AC Rate
40.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề 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
NvàW(1 ≤ N ≤ 1000,1 ≤ W ≤ 10^4). Ndòng tiếp theo: Mỗi dòng gồm hai số nguyênw[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
Community Discussion