Skills101
← All coding problems

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 n lines: 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).

Loading editor…

Log in to run and submit your code — it's free.