0/1 Knapsack

Maximize value within a weight limit, each item taken at most once.

dynamic-programming knapsack optimization dp

Write a function `knapsack_solution(weights, values, capacity)` that returns the maximum total value you can achieve by selecting a subset of items such that the total weight does not exceed the given capacity. Each item can be used at most once (0/1).

- `weights` is a list of positive integers, each representing the weight of an item.
- `values` is a list of positive integers, each representing the value of the corresponding item.
- `capacity` is a non-negative integer, the maximum total weight allowed.
- You may assume `len(weights) == len(values)`.
- Return the maximum value as an integer.

Constraints

≤ len(weights) ≤ 100
≤ capacity ≤ 1000
≤ weights[i] ≤ 100
≤ values[i] ≤ 100
Time: O(n * capacity), Space: O(capacity) is sufficient.

Example

>>> knapsack_solution([1,2,3], [6,10,12], 5)
22
>>> knapsack_solution([2,3,4,5], [3,4,5,6], 5)
7
>>> knapsack_solution([5], [10], 4)
0

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider a DP array where dp[w] is the maximum value achievable with total weight exactly w.

Initialize dp with -infinity or 0 and update from high weight to low to avoid reusing items.

The answer is the maximum dp[w] over w ≤ capacity.

Simpler top-down with memoization is also possible, but the iterative 1D DP is concise.

Test Results

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