Unbounded Knapsack
easyDynamic Programming II+10 XPTime limit 3s
A shop sells n kinds of snack packs. Pack kind i weighs w grams and gives v units of energy, and the shop has unlimited stock of every kind. Your bag holds at most W grams. What is the maximum total energy you can carry?
Input:
- line 1:
n W - next
nlines:w v
Output: the maximum total energy (0 if nothing fits).
Constraints: 1 ≤ n ≤ 100, 1 ≤ W ≤ 10⁴, 1 ≤ w ≤ 10⁴, 0 ≤ v ≤ 10⁶. The answer fits in a 64-bit integer.
Think about it: like 0/1 knapsack, but an item may be reused, so best[c] = max(best[c], best[c − w] + v) is filled from low c to high c — then best[c − w] may already contain the same item. O(n · W).
Sample input 1
2 3 1 1 2 3
Sample output 1
4
Sample input 2
3 8 1 10 3 40 4 50
Sample output 2
100
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).