Bài toán cái túi

View as PDF

Submit solution

Points: 200.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Trong siêu thị có ~n~ đồ vật ~(N≤1000)~, đồ vật thứ ~i~ có trọng lượng là ~W[i]≤1000~ và giá trị V[i] ≤1000. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng ~M (M≤1000)~. Hỏi tên trộm sẽ lấy đi những đồ vật nào để được tổng giá trị lớn nhất. Giải quyết bài toán trong trường hợp mỗi vật chỉ được chọn một lần.

Dữ liệu vào: Dòng 1: ~N, M~ cách nhau ít nhất một dấu cách

  • ~N~ dòng tiếp theo: Mỗi dòng gồm 2 số ~W_i, V_i~, là chi phí và giá trị đồ vật thứ ~i~.

Kết quả ra: Ghi giá trị lớn nhất tên trộm có thể lấy.

Ví dụ:
Input:
5 13
3 4
4 5
5 6
2 3
1 1
Output:
16 4
1
2
3
5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.