Knapsack

Knapsack problems ask how to choose items under a limited capacity. Each item usually has a cost, weight, or size, and may also have a value.

Knapsack is a standard way to learn choice-based dynamic programming.

Core Idea

For each item, the algorithm decides whether to take it or skip it. The state must remember enough information to respect the capacity limit.

In 0/1 knapsack, each item can be used at most once.

A typical state is: the best value after considering some prefix of the items with a certain capacity. The transition compares skipping the current item with taking it if it fits.

Function Contract

knapsack(weights, values, capacity) expects weights and values to have the same length and capacity to be a non-negative integer.

It returns the maximum total value that fits within the capacity when each item can be chosen at most once.

Python Example

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
 
    for weight, value in zip(weights, values):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(dp[current], dp[current - weight] + value)
 
    return dp[capacity]

The capacity loop goes backward so the same item is not reused in the same iteration.

Why the Loop Goes Backward

In 0/1 knapsack, each item can be used at most once. When using a 1D table, dp[current - weight] should come from the previous item stage, not from the current item already being processed.

Looping capacity downward preserves that rule:

for current in range(capacity, weight - 1, -1)

If the loop went upward, the same item could update a smaller capacity and then be used again for a larger capacity in the same item iteration.

2D State Version

The 1D version is easier to misuse. The conceptual 2D state is:

dp[i][c] = best value using the first i items with capacity c

Then item i is either skipped or taken. The 1D version is a memory optimization of that idea.

Complexity

For n items and capacity C, the 1D implementation runs in O(n * C) time and uses O(C) space.

This is efficient only when C is manageable. Knapsack DP can be too large if capacity is a huge number, even when the item count is modest.

Failure Example

If the 0/1 knapsack capacity loop goes upward, the same item can be used more than once during one item iteration. That accidentally turns the solution toward an unbounded-knapsack rule.

The backward loop is not an implementation detail. It preserves the contract that each item may be chosen at most once.

Common Confusions

0/1 knapsack and unbounded knapsack use different loop directions. Reusing an item changes the recurrence.

The capacity value may make the DP table large even when the number of items is small.

Another confusion is treating weight and value as the same thing. Weight consumes capacity. Value is what the algorithm tries to maximize.

When To Use It

Use knapsack reasoning when each choice consumes a limited resource and the algorithm must optimize value, count, or feasibility under that limit.

Common variations include subset sum, partition problems, bounded item counts, and unbounded item reuse.

The Main Point

Knapsack DP is about choices under capacity. The loop direction encodes whether an item may be reused.