You are packing a backpack of capacity W for an expedition with n candidate supply items. Item i has weight w_i and value v_i; each item may be taken at most once (you either bring it or you don't). Choose a set of items whose total weight does not exceed W, maximizing total value.
Line 1: two integers n W.
Line 2: n space-separated integers, the item weights (empty if n = 0).
Line 3: n space-separated integers, the item values (empty if n = 0).
A single integer: the maximum total value achievable within capacity W.
Example 1
Input
4 10 2 3 4 5 3 4 5 6
Expected
13
Explanation
Taking items 1, 2 and 4 (weights 2+3+5=10, values 3+4+6=13) fits exactly and gives the best value, 13.
Example 2
Input
2 1 5 5 10 10
Expected
0
Explanation
Every item weighs 5 but the capacity is only 1, so nothing fits: answer 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →