A warehouse has one crate of each SKU and a van with a hard kilogram cap. Dispatch wants the load with the highest declared value that still fits. The intern writes a recursion: for crate i, take it or leave it, then do the same for the rest. Three SKUs compile. Two hundred SKUs are 2^200 subsets. The van does not wait for a power set.
The same job shows up as a feature-flag budget: each flag costs RAM, each flag exists once, the process has a heap cap. Still pick or skip. Still a subset for every combination.
0/1 knapsack is pick or skip — each item exists once. You do not take half a crate. You do not restock the same SKU from an infinite bin. At item i with remaining capacity w, the only legal moves are skip, or pick if weight[i] <= w.
This post is that table. Greedy-versus-DP vocabulary, families, and the catalog live on the Algorithms Roadmap. You may call this classic DP; you do need a table (or a 1D roll of one). The layout is already two arrays — weights and values. The procedure is the fill.
The recursion that tries every subset
Nobody writes 2^n because they love branching. They write it because the spec says “each crate at most once” and the obvious model is “decide this one, then the rest.”
static int knapsackNaive(int[] weight, int[] value, int i, int remaining) {
if (i == weight.length || remaining == 0) {
return 0;
}
int skip = knapsackNaive(weight, value, i + 1, remaining);
int pick = 0;
if (weight[i] <= remaining) {
pick = value[i] + knapsackNaive(weight, value, i + 1, remaining - weight[i]);
}
return Math.max(skip, pick);
}Correct for 0/1. Each call forks. Overlapping subproblems — “first i items, capacity w” — are re-solved from scratch. Memoizing the pair (i, w) is already the DP. Filling a table in order is the same recurrence without the call stack.
Every subset is the wrong primitive once n is a catalog, not a packing list of three. The move is to index the decision by items used and capacity left.
The invariant: first i items, capacity w
dp[i][w] is the best value using the first i items with remaining capacity w. Row 0 is no items: value 0 for every w. Column 0 is no room: value 0 for every i.
At item i (1-based in the table, weight[i - 1] in Java), any feasible load is either:
- the best load that skipped this item:
dp[i - 1][w], or - this item plus the best load from the previous items with
w - weight[i]left — only legal when the item fits.
You do not need every subset of the first i items. You need the best value for this (i, w). Then:
dp[i][w] = max(skip, pick) — pick only when the item fits.
skip = dp[i - 1][w]
pick = dp[i - 1][w - weight[i]] + value[i] // if weight[i] <= w
dp[i][w] = max(skip, pick)After the last item and full capacity, dp[n][W] is the answer. Unused kilograms are allowed: leftover capacity is a legal load, just not a higher value.
Note: This is optimal substructure with a 2D memory. It is DP in the sense the roadmap uses the word. Weights and values are non-negative. A negative weight (or a “take this and gain room”) is a different model; do not feed it to this fill.
A walk: three crates, capacity 5
Three SKUs, van cap 5. The answer is A + B: weight 5, value 7. C alone is 5. A + C and B + C overweight.
item weight value
A 2 3
B 3 4
C 4 5
w: 0 1 2 3 4 5
i = 0 0 0 0 0 0 0
i = 1 0 0 3 3 3 3 // A (2, 3)
i = 2 0 0 3 4 4 7 // B (3, 4) — A+B at w = 5
i = 3 0 0 3 4 5 7 // C (4, 5) — C at w = 4, A+B still wins at 5At i = 2, w = 5: skip is 3 (A only). Pick B uses 3 kg and looks up dp[1][2] = 3, then 3 + 4 = 7. Pick. At i = 3, w = 5: skip is already 7. Pick C looks up dp[2][1] = 0, then 0 + 5 = 5. Skip C. The cell does not store the crates — only the value. Reconstruction is a later walk on the same table.
Greedy by value/weight takes C first (density 1.25) and stops at 5. Optimal is 7. Density order is the fractional algorithm. It is not 0/1.
Java: the 2D table
There is no Arrays.knapsack. The JDK map on the roadmap lists sorts, binary search, shuffle, and queues. This job is a nested fill you write.
Same spec as the walk: n items, capacity W, return best value. Row i means the first i items (weight[0] through weight[i - 1]).
static int knapsack(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
int wItem = weight[i - 1];
int vItem = value[i - 1];
for (int w = 0; w <= capacity; w++) {
int skip = dp[i - 1][w];
int pick = skip;
if (wItem <= w) {
pick = dp[i - 1][w - wItem] + vItem;
}
dp[i][w] = Math.max(skip, pick);
}
}
return dp[n][capacity];
}On the walk, dp[3][5] is 7. Empty catalog (n == 0) or capacity == 0 returns 0 without a special case: the zero row and zero column already say so.
Note: Sums of int values can overflow. If the domain is money or scores that do not fit in 32 bits, use long for value and for every dp cell. Overflow is Java’s wrap, not knapsack’s failure mode. Negative capacity is not a remaining-capacity: throw at the method boundary.
Not fractional, not unbounded
Three knapsacks share a name and split on the pick rule. Mixing them is the production bug.
0/1 (this post). Each item exists once. Pick or skip. The table above.
Fractional. You may take a fraction of an item. Then sort by value/weight and fill — a greedy, not this DP. Half a crate is legal there. It is not legal in a van that ships whole SKUs.
Unbounded. The same item may be picked again. That is Coin Change — the unbounded sibling, later in the series. Do not turn this fill into min-coins or combination counts. The tell in code: a 1D array updated forward over capacity reuses an item. The tell in the spec: “as many of each denomination as you want.”
Not half a crate, not an infinite bin. Name the pick rule at the method boundary. The recurrence is the spec.
Optional: roll to 1D, capacity backwards
Row i only reads row i - 1. You can keep one int[] of length W + 1 if you overwrite from the right: large w first. Then dp[w - wItem] is still the previous item’s value, because that slot has not been updated yet for the current item.
static int knapsack1D(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
int wItem = weight[i];
int vItem = value[i];
for (int w = capacity; w >= wItem; w--) {
dp[w] = Math.max(dp[w], dp[w - wItem] + vItem);
}
}
return dp[capacity];
}Same walk, after A then B then C, dp[5] is still 7. Going ascending in w for item A would set dp[2] = 3 and then dp[4] = dp[2] + 3 = 6 — A twice. That is unbounded, not 0/1.
Note: Iterate capacity backwards or you reused the item. Keep the 2D table if you still need to walk back which crates went in. The 1D roll remembers values, not choices.
Recovering which crates went in
The scalars answer “how much.” Loading the van needs “which SKUs.” Keep the 2D table. Walk from dp[n][W]. If dp[i][w] equals dp[i - 1][w], item i was skipped. Otherwise it was picked: record it, subtract its weight, continue.
static int[] knapsackItems(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
int wItem = weight[i - 1];
int vItem = value[i - 1];
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i - 1][w];
if (wItem <= w) {
dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wItem] + vItem);
}
}
}
int[] tmp = new int[n];
int count = 0;
int w = capacity;
for (int i = n; i >= 1; i--) {
if (dp[i][w] != dp[i - 1][w]) {
tmp[count++] = i - 1;
w -= weight[i - 1];
}
}
int[] picked = new int[count];
for (int k = 0; k < count; k++) {
picked[k] = tmp[count - 1 - k];
}
return picked; // 0-based indices, catalog order
}On the walk, dp[3][5] == dp[2][5], so C is skipped. dp[2][5] != dp[1][5], so B is picked and w becomes 2. dp[1][2] != dp[0][2], so A is picked. Indices {0, 1}.
Note: On a value tie, != prefers skip. If the spec wants a particular set among equals, store a choice bit per cell; do not pretend the numbers remembered a preference they never stored.
Complexity
| What | Cost | Why |
|---|---|---|
| Time | O(n · W) | One cell per item and capacity slot |
| Extra space (2D) | O(n · W) | Full table; needed if you reconstruct |
| Extra space (1D) | O(W) | One row; values only |
| Naive subsets | O(2^n) | Every pick-or-skip path |
| Output | O(1) or O(k) | The value, or k picked indices |
W is the capacity in the same units as the weights. This is pseudo-polynomial: fine when W is a van in kilograms, painful when W is a 64-bit budget. The input arrays are O(n) whoever owns them. A 2D fill, or a 1D roll backwards — no JDK helper. A correct power set is still the wrong default on a catalog.
When not to use 0/1 knapsack
Skip this fill when the job is not “each item at most once, integer capacity, maximize value.”
- You may take a fraction. Sort by value/weight and fill. That greedy is optimal for fractional; it is wrong for 0/1 (C-first scored
5on the walk; A+B scored7). - The same item may repeat. That is unbounded — Coin Change, later. Do not teach min-coins here; do not run the 1D loop forward and call it 0/1.
- The picks must be contiguous. Maximum subarray is Kadane, already in this series. Knapsack may skip the middle SKU; Kadane may not punch a hole in a slice.
- The job is a shared subsequence or an edit grid. LCS and edit distance are later Wave 6 posts. They are different recurrences. Do not stretch
dp[i][w]to cover them. - Capacity is huge and n is tiny.
O(n · W)loses to meet-in-the-middle or to “just enumerate” whennis 20 andWis10^12. The table’s second axis has to fit in memory. - Items have dependencies, counts as a goal, or extra dimensions. “Must take A if you take B,” “count the loads,” “weight and volume caps” are other bills — backtracking, unbounded counts, or contest-only DP this series leaves on the table.
Pick or skip, each item once, one capacity — that is the job. Anything else is a different procedure that may look like a knapsack.
Cheat sheet
Job: maximize value; each item at most once; capacity W
Invariant: dp[i][w] = max(skip, pick if weight fits)
Skip / pick: dp[i-1][w] vs dp[i-1][w - wt] + val
1D roll: for w from W down to wt: dp[w] = max(dp[w], dp[w-wt] + val)
Reconstruct: walk i = n .. 1; if dp[i][w] != dp[i-1][w], take i, w -= wt
Time/space: O(n·W) / O(n·W) or O(W) extra
JDK: none — write the fill
Not this: fractional greedy, unbounded / coin change, Kadane, LCS, editDo:
- Name the pick rule first: 0/1, fractional, or unbounded.
- Fill
dp[i][w]from smalleri, or roll 1D backwards overw. - Keep the 2D table if the caller needs the SKUs, not only the value.
- Use
longwhen the total value may not fit inint.
Don’t:
- Enumerate every subset once
nis a catalog. - Iterate the 1D array forward and still claim each item is used once.
- Sort by density and call it 0/1 — that is fractional.
- Quote this fill for coin change, Kadane, LCS, or an edit-distance grid.
Wrap-up
0/1 knapsack replaces “every subset” with one decision per item and remaining capacity: skip, or pick if it fits. A table of dp[i][w] (or a 1D roll filled backwards) keeps the recurrence; the answer is the last cell. Fractional takes a slice of an item; unbounded reuses one — neither is this fill. When you need the crates, walk the 2D table back from dp[n][W].
The layout was already two arrays. The procedure is this fill. When the item can repeat, that is a different named procedure — start from the Algorithms Roadmap and pick the job again, or continue to coin change.