0/1 Knapsack Solver

Understanding the 0/1 knapsack solver — concept and principle

The 0/1 knapsack problem asks: given items with weights and values and a bag with a weight limit, which items should you take to get the most value? Each item is either taken whole or left behind. The same structure appears in budgeting, project selection and cargo loading. This solver finds the exact optimum by dynamic programming.

How it is calculated

Let D[i][c] be the best value using only the first i items with capacity c.

• D[0][c] = 0.
• D[i][c] = D[i−1][c] (skip item i), or, if wᵢ ≤ c, max(D[i−1][c], D[i−1][c − wᵢ] + vᵢ) (take item i).
• The maximum value is D[n][capacity].

To list the chosen items, the solver walks back: whenever D[i][c] differs from D[i−1][c], item i was taken and c drops by wᵢ. Weights are rounded to integers, both lists must have the same length, and capacity is limited to 100,000.

The principle

For the last item there are only two choices: leave it, or take it and solve the rest with less capacity. The best answer for the whole problem is the better of those two, and each depends only on smaller subproblems (fewer items, smaller capacity). The table has (n + 1) × (capacity + 1) cells, so the time is O(n · W). This is called pseudo-polynomial, because W is a number, not an input size; knapsack is NP-hard in general, so no known method is fast for every input with huge capacities.

Worked example

1. Inputs: weights 1, 3, 4, 5; values 1, 4, 5, 7; capacity 7.
2. The table's last row for capacities 0–7 is 0, 1, 1, 4, 5, 7, 8, 9, so the maximum value is 9.
3. Trace-back picks item 3 (weight 4, value 5) and item 2 (weight 3, value 4): total weight 7, value 9, so items 2, 3.
4. Compare the greedy approach by value per weight: item 4 (7 ÷ 5 = 1.4) first, then item 1 fits in the remaining 2 units, for only 8. Greedy is not optimal.

How to read the result

The result is the exact best value for the given numbers. If several combinations tie, the solver reports one of them. Try nearby capacities to see how much extra value one more unit of capacity would buy; here capacity 8 would allow items 2 and 4 for a value of 11.

Common mistakes

• Entering decimal weights; they are rounded, so scale them first (e.g. 1.25 kg as 125 in units of 10 g).
• Confusing it with the fractional knapsack, where items can be split and greedy by value per weight is optimal.
• Using it for items that can be taken many times; that is the unbounded knapsack.

Frequently asked questions

Why can't I just sort by value per weight?

That greedy rule can leave unused capacity, as the example shows; it is only optimal when items can be split.

Is the knapsack problem NP-complete?

Its decision version is, as shown by Karp in 1972, but the dynamic program is fast when capacities are moderate.

How much memory does it use?

About (n + 1) × (capacity + 1) numbers; the value alone can be found with a single row of capacity + 1.

Sources: R. M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, Plenum Press, 1972 · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (dynamic programming, greedy algorithms)