CTDL> bài 26.A5 CTDL> bài Bài toán cái túi.
Bài toán cái túi.
Một tên trộm có 1 cái túi có thể mang các đố vật với trọng lượng tối đa là V. Hiện tại tên trộm muốn lựa chọn các đồ vật trong N đồ vật để ăn trộm, mỗi đồ vật có trọng lượng là w[i] và giá trị là v[i]. Hãy xác định tổng giá trị lớn nhất của các đồ vật mà tên trộm này lựa chọn sao cho trọng lượng của chúng không vượt quá V.
Input Format
Dòng đầu ghi 2 số N và V. Dòng tiếp theo ghi N số của mảng w. Sau đó là một dòng ghi N số của mảng c.(V<=1000; N≤1000; 1<=w[i], c[i]<=500)
Constraints
.
Output Format
In ra giá trị lớn nhất có thể đạt được.
Ví dụ:
Dữ liệu vào
6 28
41 17 34 3 19 24
4 4 7 8 3 36
Dữ liệu ra
44
Comments