0/1 Knapsack
easyDynamic Programming II+10 XPTime limit 2s
A trekker's bag can carry at most W kilograms. There are n items; item i weighs w kg and is worth v points. Each item can be taken at most once (you can't take half an item). Which items maximise the total worth without going over W? Print that maximum worth.
Input:
- line 1:
n W - next
nlines:w vfor each item
Output: the maximum total worth.
Constraints: 1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴, 1 ≤ w ≤ 10⁴, 0 ≤ v ≤ 10⁶.
Think about it: best[c] = the best worth using capacity c. For each item, update best[c] = max(best[c], best[c − w] + v) going from high c to low c, so the item is used at most once. O(n · W). Trying all 2ⁿ subsets is hopeless for n = 100.
Sample input 1
4 7 1 1 3 4 4 5 5 7
Sample output 1
9
Sample input 2
3 5 6 10 7 20 8 30
Sample output 2
0
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).