KNAP - Ăn trộm thông minh
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Một kẻ trộm đột nhập vào một cửa hiệu tìm thấy có ~n~ món hàng có trọng lượng và giá trị khác nhau, nhưng hắn chỉ mang theo một cái túi có sức chứa về trọng lượng tối đa là ~M~. Vậy kẻ trộm nên bỏ vào ba lô những món nào để đạt giá trị cao nhất trong khả năng mà hắn có thể mang đi được.
Input
- Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~M\ (1 ≤ n, M ≤5000)~;
- ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~x~ và ~y~ mô tả một đồ vật có trọng lượng ~x~ và giá trị ~y\ (1 ≤ x ≤ M, 1 ≤ y ≤10000)~.
Output
- In ra tổng giá trị lớn nhất đạt được.
Sample
Input #1
10 50
33 6
19 3
12 8
22 7
18 3
34 10
14 10
21 9
26 10
40 4
Output #1
27
Problem source: Kc97ble - Free Contest
Bình luận
có ai bị wr test 20 ko ạ
Adu! Tiep tay cho trom