Knapsack Variants & the Van Loader
In short: every knapsack is one table with four dials you can turn: how
many of each item you may take (once, unlimited, or up to c), what a cell
means (at most, exactly or at least a capacity), how two choices combine
(max, min, or or +), and how many limits apply at once. The loop
direction decides "once" versus "unlimited" — downward reads the row before
this item touched it, upward lets the same item feed itself again. Everything
else about knapsack is naming which four settings your problem needs.
Meridian's first van of the day leaves at seven. It can carry 12 kg and its cargo bay holds 11 litres, and the morning's parcels each pay a delivery fee. A heavy little parcel of engine parts and a light but bulky roll of carpet are competing for the same van on two different limits at once. Choosing which parcels go is a knapsack problem. It isn't quite the one you have already solved, though.
You built the 0/1 knapsack table for Tunebox and squeezed it into one row by looping capacity downward. This lesson treats that table as the parent of a family. Almost every knapsack you'll meet changes one of four things, and once you can name which one, you can write the variant without memorising it.
Four dials on one table
| Dial | Choices | Example |
|---|---|---|
| How many of each item | once (0/1), unlimited, or up to c copies |
one parcel; a crate size in stock forever; five spare tyres |
| What a cell means | at most w, exactly w, at least w |
a weight limit; a calibration pallet; a ride quota |
| How cells combine | max, min, or, + |
best fee; fewest crates; is it possible; how many ways |
| How many limits | one capacity, or several | kg only; kg and litres; kg and a slot count |
Now the van loader is easy to place: once each, at most, max, and two
limits. The rest of this lesson turns each dial in turn.
Dial 1: once, unlimited or limited
The one-row table from the tabulation lesson reads best[w - kg] and writes
best[w]. Which value it reads depends only on the direction of the loop. Here
is the same parcel (2 kg, fee 3) folded into an empty row twice, once in each
direction:
Downward, every read lands on a cell this parcel hasn't touched yet. Upward, the reads land on cells it has just written, so the same parcel is loaded again and again.
Downward starts at 6 kg. It reads best[4], which this parcel hasn't touched, so the cell becomes 3 + 0 = 3. 2 by 7 table. At row 0, column 6 — value 3. 14 of 14 cells filled.
So one keyword picks between two problems. Loop downward for 0/1 and
upward for unlimited. The unlimited version also answers "fewest crates to
make exactly 13 litres", where you can reuse any crate size as often as you
like. Only the combine step changes, to min and + 1:
Step through a smaller version and watch the "not yet" sentinel get replaced from the left:
Now build the full two-dimensional version yourself, with one row per crate size. In the unbounded table a cell reads the cell to its left in the same row, and that one arrow is the whole difference from 0/1, which reads the row above. Change the sizes or the target and run it again:
Your unbounded table. A cell may read its own row to the left, and that is how a crate size gets used more than once.
Limited stock sits between the two. A thousand bolts as a thousand 0/1 items would mean a thousand passes. Instead, split the copies into bundles of 1, 2, 4, … plus whatever is left, and treat each bundle as one 0/1 item:
copies, k, bundles = 10, 1, []
while copies > 0:
take = min(k, copies)
bundles.append(take)
copies -= take
k *= 2
print(bundles)Dial 2: at most, exactly, at least
The starting values decide what a cell means, and the loop can stay exactly
as it is. Starting from all zeros means "at most w", because an empty van is a
legal answer for every capacity. The crane calibration run needs a pallet
weighing exactly 5 kg, though:
cap = 5
parcels = [[2, 6], [4, 9]] # kg, fee
best = [0] * (cap + 1)
for kg, fee in parcels:
for w in range(cap, kg - 1, -1):
best[w] = max(best[w], fee + best[w - kg])
print(best[5])At least is the third meaning, and it turns up whenever overshooting is allowed but wasteful. Here it is as an interview-style problem, in the form you'd be handed one.
Interview-style problem: the ride quota. Meridian's drivers ride the tram between depots. The tram sells ride bundles
[rides, price], and each bundle can be bought any number of times. Given the bundles and a quotarides, return the lowest price that covers at leastridesrides.Constraints: 1 to 6 bundles, each with 1 to 50 rides;
0 ≤ rides ≤ 500.Examples: bundles
[[1, 3], [5, 12], [12, 25]]with quota 11 →25, because one 12-ride bundle beats 5 + 5 + 1 (price 27). Bundles[[2, 5]]with quota 7 →20, four bundles and one wasted ride.
The only new line is a clamp. A bundle of n rides that meets a quota of r
leaves max(0, r - n) still to cover, never a negative number. You'll write it
as this lesson's capstone exercise.
Dial 3: what a cell combines
| Question | Combine | Start | Empty-set cell |
|---|---|---|---|
| best total fee | max |
0 (at most) or -inf (exact) |
0 |
| fewest items | min of … + 1 |
inf |
0 |
| is it possible | or |
False |
True |
| how many ways | + |
0 | 1 |
The "no answer yet" value must be one the operator ignores: max ignores
-inf, min ignores inf, or ignores False and + ignores 0.
❓ Cross-question: "Why not pack by fee per kilo?" That's only optimal when you may take part of an item, like fuel. With whole parcels and a second limit, greedy can't see how pieces fit together.
Dial 4: a second limit is a second index
The van loader has two limits, so the state needs both: best[i][w][v] is the
highest fee from the first i parcels within w kg and v litres. The
choice is still leave or load, and a parcel can only be loaded if it fits on
both limits:
Every extra limit multiplies the table: two limits of 100 give 10,000 cells per
parcel. A count limit ("exactly k parcels") is just another index, as your
boss exercise shows.
Here's a two-limit loader someone trimmed "for speed". The rug is 9 litres and the bay holds 8, so the rug should never be loaded:
The rug can't fit in an 8-litre bay, so the answer is 0, yet this prints 40. Stop the inner loop reading a cell that doesn't exist.
In Java, best[w][-1] throws. Python quietly reads the last column, so tie
every loop's lower bound to the item's size on every limit.
Why the table beats trying every subset
The table costs n · W · V cells, while trying every subset costs 2ⁿ.
Neither is always smaller. For a van with limits of 100 kg and 100 litres the table
has n × 10,000 cells:
| parcels n | every subset (2ⁿ) | table (n × 10,000) |
|---|---|---|
| 10 | 1,024 | 100,000 |
| 17 | 131,072 | 170,000 |
| 18 | 262,144 | 180,000 |
| 30 | 1,073,741,824 | 300,000 |
Below 18 parcels brute force is actually smaller, which is why tiny inputs are often solved by enumeration. Above it the gap doubles with every parcel, and at 30 parcels brute force is about 3,600 times the table. The table's cost grows with the numbers in the limits, not just the count of parcels, so a limit measured in grams instead of kilograms makes it 1,000 times wider. That is what "pseudo-polynomial" means.
Every cell does one max (or min) of a constant number of neighbours, and there
are n parcels times the capacity cells, so the full table costs O(n · W) time
(or O(n · W · V) with two limits). Folding it into one row keeps only the
layer being written, which is O(W) space — the trade is that you can no
longer walk back to see which parcels won, which is why the van loader keeps
the full table instead.
| Variant | Loop | Time | Space (one row) |
|---|---|---|---|
| 0/1 | downward | O(n · W) | O(W) |
| unbounded | upward | O(n · W) | O(W) |
| bounded, binary split | downward per bundle | O(W · Σ log cᵢ) | O(W) |
| two limits | downward on both | O(n · W · V) | O(W · V) |
exactly k items |
downward on count and weight | O(n · k · W) | O(k · W) |
Idioms & real-world patterns
Keep the full table when you need the choice
The one-row tricks drop the history, so you can no longer walk back to find which parcels won. The van loader has to say which parcels to load, so it keeps the full three-index table and walks back from the last parcel, the same way the playlist packer did.
Quick practice
best = [0] * 7
items = [(3, 5)] # kg, fee
for kg, fee in items:
for w in range(kg, 7):
best[w] = max(best[w], fee + best[w - kg])
print(best[6])There's a single 3 kg, fee-10 parcel and a 6 kg van, so the right answer loads it once for a fee of 10. This prints 20 because the upward loop lets the same parcel feed itself a second time. Fix the loop direction.
🎯 Your turn
Write load_van(parcels, max_kg, max_litres). Each parcel is
[id, kg, litres, fee] and can be loaded at most once. Choose parcels with total
weight ≤ max_kg and total volume ≤ max_litres and the highest total fee.
Return {"fee": …, "kg": …, "litres": …, "parcels": ids_in_input_order}.
load_van([["P1", 4, 3, 30], ["P2", 3, 5, 26], ["P3", 2, 2, 17]], 6, 6)→{"fee": 47, "kg": 6, "litres": 5, "parcels": ["P1", "P3"]}
Ties: build the full table best[i][w][v] and walk back from the last
parcel. A parcel was loaded only when its layer's fee differs from the layer
before.
Then press ▶ Run, tap the Live App try chips, and hit ✓ Check. Green means the van loader is built. ✅