Knapsack 2
Xem dạng PDF
Gửi bài giải
Điểm:
35,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
There are N items, numbered ~1, 2,..., N~. For each ~i~ ~(1 ≤ i ≤ N)~, Item ~i~ has a weight of ~w_i~ and a value of ~v_i~ Taro has decided to choose some of the ~N~ items and carry them home in a knapsack. The capacity of the knapsack is ~W~, which means that the sum of the weights of items taken must be at most ~W~. Find the maximum possible sum of the values of items that Taro takes home.
Constraints
• All values in input are integers.
• ~1 ≤ N ≤ 100~
• ~1 ≤ W ≤ 10^9~
• ~1≤ w_i≤W~
• ~1 ≤ v_i ≤ 10^3~
Input
- Input is given from Standard Input in the following format:
~N~ ~W~
~w_1~ ~v_I~
~w_2~ ~v_2~
.
.
~w_N~ ~v_N~
Output
- Print the maximum possible sum of the values of items that Taro takes home.
Example 1
Input
3 8
3 30
4 50
5 60
Output
90
Example 2
Input
1 1000000000
1000000000 10
Output
10
Example 3
Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17
Bình luận
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.
qua lui thì chỉ có máy tính của nasa mới chạy nổi=)))))
vớt dc 0,5d:)))
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.
chủ quan quá em, a cũng k ngờ họ ra câu này, suy ra cái đảo nhãn khá khó
biết thế khi tối hqua học thuộc luôn cho rồi :))
Hetcuu
Tạch Tạch Tạch :///
{ / =((
=((
đảo nhãn nhé ˚˚
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
uk t ai eo 0.1 mà còn k dịch đc nưa là biết r =))
umm việt nam mít pờ lít
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.