CTDL&GT bài 26.A5 CTDL&GT bài Bài toán cái túi.


LÀM BÀI

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

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

There are no comments at the moment.

Zalo