Atcoder Educational DP Contest D - Knapsack 1
Xem dạng PDF
Có ~N~ đồ vật được đánh số từ ~1~ đến ~N~. Đồ vật thứ ~i~ ~(1 \le i \le N)~ có khối lượng là ~w_i~ và giá trị là ~v_i~.
Taro quyết định chọn một số đồ vật bỏ vào chiếc túi của anh mang về. Sức chứa tối đa của chiếc túi là ~W~, nghĩa là tổng khối lượng các đồ vật có thể mang tối đa là ~W~.
Hãy tìm tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.
Input
Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \le N \le 100)~ và ~W~ ~(1 \le W \le 10^5)~: số lượng đồ vật và sức chứa tối đa của chiếc túi.
~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~w_i~ ~(1 \le w_i \le W)~ và ~v_i~ ~(1 \le v_i \le 10^9)~ lần lượt là khối lượng và giá trị của đồ vật thứ ~i~.
Output
Xuất ra tổng giá trị các đồ vật lớn nhất mà Taro có thể mang về nhà.
Sample 1
Input
3 8
3 30
4 50
5 60
Output
90
Chọn đồ vật ~1~ và ~3~. Tổng khối lượng sẽ là ~3 + 5 = 8~ và tổng giá trị là ~30 + 60 = 90~.
Sample 2
Input
5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
5000000000
Kết quả có thể vượt quá giới hạn kiểu số nguyên ~32~-bit.
Sample 3
Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17
Chọn đồ vật ~2~, ~4~ và ~5~. Tổng khối lượng sẽ là ~5 + 6 + 3 = 14~ và tổng giá trị là ~6 + 6 + 5 = 17~.
Bình luận
Bài này code python có ac được không vậy?
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
.
Bài này bạn nên dùng quy hoạch động cái túi để làm nhé.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.