01 Knapsack

0/1 Knapsack

You have a bag that holds a fixed capacity of weight, and a set of items each with a weight and a profit. Each item is take-it-or-leave-it — you cannot take a fraction, and you cannot take the same item twice (that is the “0/1”). The mechanism that solves it: walk the items one at a time, and for each remaining capacity remember the best profit reachable so far — so the same sub-question (best profit for the first i items under capacity c) is answered once and reused, instead of re-exploring every subset.

Problem

Given profits[] and weights[] for N items and an integer capacity, return the maximum total profit of a subset whose total weight does not exceed the capacity.

Why brute force explodes

Each item is in or out, so there are 2^N subsets. Enumerating them is O(2ⁿ) — 40 items is already a trillion. But most of those subsets re-ask the same question, which is the signal for dynamic programming.

The recurrence

Define dp[i][c] = the best profit using only the first i items with a capacity budget of c. For item i there are exactly two futures:

• Skip it — the answer is whatever you could do with the previous items: dp[i-1][c].
• Take it (only if it fits, weights[i] ≤ c) — earn its profit and spend its weight, then solve the smaller problem: profits[i] + dp[i-1][c - weights[i]].

Keep the better of the two: dp[i][c] = max(skip, take). The base row (0 items) is all zeros. The final answer is dp[N][capacity].

Traced example

profits [1, 6, 10, 16], weights [1, 2, 3, 5], capacity 7. Fill the table row by row; each cell uses only the row directly above it.

Reading dp[4][7] = 22: the winning subset is the item of weight 2 (profit 6) plus the item of weight 5 (profit 16) — total weight 7, profit 22. Notice how dp[4][7] was built from dp[3][2] (=6) by taking the weight-5 item: 16 + 6 = 22, which beat skipping it (dp[3][7] = 17).

Step through it yourself

The debugger below fills this exact table cell by cell — the same items and capacity. Press Play and at each cell where the item fits you’ll be asked to predict skip vs take before the answer is revealed; the final pass back-traces which items ended up in the knapsack.

Code — three forms, same recurrence

Top-down (memoized recursion) — writes the recurrence directly, caches each (i, c):

int solveKnapsack(int[] profits, int[] weights, int capacity) {
    Integer[][] memo = new Integer[profits.length][capacity + 1];
    return knap(profits, weights, capacity, 0, memo);
}

int knap(int[] p, int[] w, int cap, int i, Integer[][] memo) {
    if (i == p.length || cap == 0) return 0;
    if (memo[i][cap] != null) return memo[i][cap];
    int skip = knap(p, w, cap, i + 1, memo);
    int take = 0;
    if (w[i] <= cap) take = p[i] + knap(p, w, cap - w[i], i + 1, memo);
    return memo[i][cap] = Math.max(skip, take);
}

Bottom-up (tabulation) — fills the table shown above, no recursion:

int solveKnapsack(int[] profits, int[] weights, int capacity) {
    int n = profits.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];                       // skip item i-1
            if (weights[i - 1] <= c)                        // does it fit?
                dp[i][c] = Math.max(dp[i][c],
                            profits[i - 1] + dp[i - 1][c - weights[i - 1]]);
        }
    }
    return dp[n][capacity];
}

Space-optimized (1-D) — each row only reads the row above, so one array suffices. The capacity loop runs backwards; that is what enforces “each item used at most once” (a forward loop would let an item be re-picked, which is the unbounded knapsack):

int solveKnapsack(int[] profits, int[] weights, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < profits.length; i++)
        for (int c = capacity; c >= weights[i]; c--)        // reverse = 0/1
            dp[c] = Math.max(dp[c], profits[i] + dp[c - weights[i]]);
    return dp[capacity];
}

Complexity — from first principles

The table has (N+1) × (capacity+1) cells and each is computed in O(1) (one comparison of two already-known cells). So:

time  = O(N × capacity)
space = O(N × capacity)  →  O(capacity) with the 1-D trick

The subtle part: this is pseudo-polynomial, not polynomial. The cost scales with the numeric value of capacity, not with the input size in bits. Double the capacity and you double the work; a capacity of 10⁹ makes the table astronomically large even for a handful of items. So DP knapsack is the right tool when capacity is modest, and a red flag when it is huge.

Pitfalls

• Forward loop in the 1-D version. Iterating capacity ascending lets the same item be counted multiple times — that silently solves unbounded knapsack instead. 0/1 requires the descending loop.
• Off-by-one between item index and dp row. In the 2-D form dp[i] covers the first i items, so item i lives at weights[i-1]. Mixing the two indexings is the classic bug.
• Assuming polynomial time. See above — huge capacities kill it; that is a “switch approach” signal, not something to optimize your way out of.
• Treating it like fractional knapsack. The greedy “best profit-to-weight ratio first” is optimal for the fractional problem but wrong for 0/1 — indivisibility breaks greedy.

When to use it — and when not

Reach for 0/1 knapsack DP when you must make independent take/leave decisions under a single capacity/budget constraint to maximize a sum, and the capacity is a modest integer. The tells: “choose a subset”, “without exceeding”, “maximize total value”.

• vs. Greedy (ratio-first): greedy is O(N log N) and gives the optimum for fractional knapsack, but is wrong for 0/1. Use greedy only when items are divisible.
• vs. Unbounded knapsack: same table, but items are reusable → the take branch stays on the current row (dp[i][c - w]) / the 1-D loop goes forward. Pick unbounded when an item can be chosen any number of times (coin change, rod cutting).
• vs. Meet-in-the-middle / branch-and-bound: when capacity is enormous but N is small (≤ ~40), the O(N×capacity) table is infeasible; split the items and combine halves in O(2^(N/2)) instead.

Takeaways

• Each cell is one binary choice — max(skip, take) — and sortedness of the recurrence (row i depends only on row i-1) is what lets you drop to O(capacity) space.
• Time O(N×capacity) is pseudo-polynomial: fast for small capacities, hopeless for huge ones.
• The 1-D loop direction is the difference between 0/1 (reverse) and unbounded (forward).
• Greedy is a trap here; indivisibility means you need the table.

---

Re-authored and deepened for this guide. Sources: DesignGurus “Grokking Dynamic Programming Patterns” (problem framing); CLRS ch. 15 and Kleppmann-style first-principles treatment for the recurrence, pseudo-polynomial analysis, and the 0/1-vs-unbounded loop-direction distinction.

I just read a lesson on **01 Knapsack** (DSA) and want to truly understand it. Explain 01 Knapsack from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **01 Knapsack** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **01 Knapsack** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **01 Knapsack** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.