Unbounded Knapsack

Maximize value with unlimited item copies under a capacity limit.

dynamic-programming knapsack optimization

You are given a knapsack with capacity `capacity` (a non-negative integer) and a list of items. Each item has a weight and a value, both positive integers. You may take any number of copies of each item (including zero), and the total weight of the chosen copies must not exceed `capacity`. Your goal is to maximize the total value.

Write a function `max_value(capacity, weights, values)` that returns the maximum achievable total value.

- `capacity`: non-negative integer.
- `weights`: list of positive integers, same length as `values`.
- `values`: list of positive integers.

If no item fits (or capacity is 0), return 0.

Constraints

- 0 <= capacity <= 1000
- 1 <= len(weights) <= 20
- 1 <= weights[i] <= 1000
- 1 <= values[i] <= 1000
- Each copy must be taken whole (no fractional items).
- Expected time complexity: O(capacity * number_of_items).

Example

>>> max_value(10, [2, 3], [3, 4])
15
>>> max_value(0, [1, 2], [5, 6])
0
>>> max_value(10, [5], [10])
20
>>> max_value(7, [2, 3], [4, 5])
15

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a DP array where dp[i] is the best value for capacity i.

For each capacity, try using one copy of each item that fits.

Iterate items outer, then capacity inner, to allow unlimited copies.

Example: for each item, for cap from weight to capacity, dp[cap] = max(dp[cap], dp[cap - weight] + value).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.