0/1 Knapsack

Description

You have items with weights and values and a bag with a capacity. Each item is either taken whole or left behind. Maximizing the value means choosing among 2^n subsets, and greedy shortcuts fail. Take capacity 50 and items of (weight 10, value 60), (20, 100) and (30, 120). Taking the best value per weight first gives 60 + 100 = 160, while 100 + 120 = 220 fits. A DP over the items considered so far and the capacity used solves it exactly. Many other problems, such as subset sums, target sums and partitions, are this same table in disguise.

We'll go from simple to more technical:

1. The pattern: dp[i][cap] built from the previous row, either skip the item or take it once.
2. A second flavor: one row swept from high to low, and counting instead of maximizing.
3. Where knapsack shows up in production (budgets, packing, resource allocation).
4. What breaks it: reusing items, greedy ratios, huge capacities, parity checks.

The approach

int knapsack01(int capacity, int[] weights, int[] values) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];         // dp[i][cap] = best value from the first i items
    for (int i = 1; i <= n; i++) {
        for (int cap = 0; cap <= capacity; cap++) {
            dp[i][cap] = dp[i - 1][cap];                                   // skip item i
            if (weights[i - 1] <= cap) {
                dp[i][cap] = Math.max(dp[i][cap],
                        dp[i - 1][cap - weights[i - 1]] + values[i - 1]);  // take it - built on the PREVIOUS row
            }
        }
    }
    return dp[n][capacity];
}

def knapsack_01(capacity: int, weights: list[int], values: list[int]) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # dp[i][cap] = best value from the first i items
    for i in range(1, n + 1):
        for cap in range(capacity + 1):
            dp[i][cap] = dp[i - 1][cap]                                 # skip item i
            if weights[i - 1] <= cap:
                dp[i][cap] = max(dp[i][cap],
                                 dp[i - 1][cap - weights[i - 1]] + values[i - 1])   # take it - built on the PREVIOUS row
    return dp[n][capacity]

Both options read row i - 1: the best achievable before item i was available. That is what makes each item usable at most once. Reading dp[i][cap - w] instead would allow item i again on top of itself - unbounded knapsack: one item of weight 1 and value 1 with capacity 3 is worth 1, but the current-row version says 3.

A second flavor: one row, swept backwards - and counting

Only the previous row is ever read, so one array is enough - if capacities are swept from high to low, so dp[cap - w] still holds the previous item's value when it's read:

int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++)
    for (int cap = capacity; cap >= weights[i]; cap--)          // high to low: "previous row" preserved
        dp[cap] = Math.max(dp[cap], dp[cap - weights[i]] + values[i]);

dp = [0] * (capacity + 1)
for w, v in zip(weights, values):
    for cap in range(capacity, w - 1, -1):          # high to low (the stop is exclusive): "previous row" preserved
        dp[cap] = max(dp[cap], dp[cap - w] + v)

Swept low to high, dp[cap - w] may already include item i, and the example above again returns 3. The same 0/1 table counts as well as maximizes. Target Sum - put + or - in front of each number to reach a target - becomes "count subsets summing to P" once you notice the plus-set P and minus-set N satisfy P - N = target and P + N = total, so P = (total + target) / 2 (and there are no ways at all if that's odd or |target| > total).

Where you'll see it

Budget allocation (which projects to fund under a fixed budget), cargo and container loading, choosing which ads fill a fixed slot length, and picking features for a release under an engineering-hours cap are 0/1 knapsack. Real systems use the DP when capacities are modest integers, and switch to branch-and-bound or approximation schemes when they aren't.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does the take-option read dp[i - 1][cap - w] rather than dp[i][cap - w]?

2. In the 1D version, why must capacities be swept from high to low?

3. How does Target Sum turn into a subset-counting knapsack?

Key takeaways

• 0/1 knapsack: for each item and capacity, skip it or take it on top of the previous row.
• Reading the previous row (or sweeping a 1D table downward) is what keeps each item to one use.
• Greedy by ratio is wrong for whole items; it's only right for fractional knapsack.
• O(n * capacity) is pseudo-polynomial - fine for small capacities, hopeless for huge ones.
• The same table counts subsets: Target Sum reduces to counting subsets that sum to (total + target) / 2.