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
ib fb để xin sol
xin sol là ngon r 😥
.
t làm quay lui mong là cứu vớt dc một ít :))
qua lui thì chỉ có máy tính của nasa mới chạy nổi=)))))
vớt dc 0,5d:)))
không phải ac từ hôm qua à em ??
e trùm ngu qhd =))
công thức e lấy trên mmagj xong đi thi ko ngờ ra luôn câu này :))
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
ducminh:certainly!here's a polished English version =