Lesson 30.1 · Knapsack DP

0/1 Knapsack

dp[c] = best value with capacity c using the items seen so far. For each item, loop capacity downwards so the item is used at most once.

16 min

Think of it like this

Packing a suitcase with a weight limit: for each item you ask, "is it worth giving up this much space for it?", and the answer depends on the best packing of the remaining space.

1.From table to one row

Full table: dp[i][c] = best value using the first i items with capacity c. Skip item i: dp[i − 1][c]. Take it (if it fits): dp[i − 1][c − w] + v. Answer dp[n][C]. O(n × C) time and memory.

Each row only reads the previous row, so one array is enough, if you loop c from high to low. Then dp[c − w] still holds the previous row's value (this item not yet added). Looping upwards would let the same item be added again, which is the unbounded knapsack.

Knapsack is pseudo-polynomial: O(n × C) depends on the numeric capacity, not the input length. It's fast for C up to about 10⁵–10⁶.

Main.java

public class Main {
    public static void main(String[] args) {
        int[] w = {1, 3, 4}, v = {15, 20, 30};
        int cap = 4;

        int[] once = new int[cap + 1];
        for (int i = 0; i < w.length; i++)
            for (int c = cap; c >= w[i]; c--)                 // downwards: 0/1
                once[c] = Math.max(once[c], once[c - w[i]] + v[i]);

        int[] reuse = new int[cap + 1];
        for (int i = 0; i < w.length; i++)
            for (int c = w[i]; c <= cap; c++)                 // upwards: unbounded
                reuse[c] = Math.max(reuse[c], reuse[c - w[i]] + v[i]);

        System.out.println("each item once (loop down): " + once[cap]);
        System.out.println("items reusable (loop up):  " + reuse[cap]);
    }
}

Output

each item once (loop down): 35
items reusable (loop up):  60

▶ Dry run: Capacity 4, items (weight, value) = (1, 15), (3, 20), (4, 30)loop capacity from 4 down to the item's weight

Step 1/4No items yet: every capacity is worth 0.

Remember

State: capacity (plus items processed).
0/1: capacity loop downwards.
Unbounded: capacity loop upwards.

Common mistakes

Looping the wrong way and silently reusing items.
Using knapsack when capacity is 10⁹ (too large).

Words used in this lesson

Knapsack: Choosing items with weights and values to maximise value within a capacity.
Pseudo-polynomial: Running time that depends on the size of a number in the input (like capacity), not just the number of items.

Command Palette

0/1 Knapsack

1.From table to one row