The knapsack problem
In short: The knapsack problem picks items with the greatest total value without exceeding a weight limit; a dynamic programming table of items by weight solves it in O(n · W).
Problem
Which parcels go in the box
A courier rides a cargo bike, and its box carries up to 50 kg. Parcels are waiting at the depot. Each has a weight and a delivery fee, and the courier gets the fee for every parcel delivered. A parcel cannot be split: it is taken whole or not at all. Which parcels should the courier take to earn the most?
The programmer tries everything: for each parcel, "take" or "leave". Once every parcel is decided, the program checks whether the load fits and what it pays. The parcels come from the depot. Here we build them with a formula so they are the same in every language: weight from 1 to 20 kg, fee from 2 to 40 €.
static long tries = 0;
static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) { if (i == weight.length) { tries++; return load <= cap ? sum : -1; } int skip = tryAll(weight, fee, cap, i + 1, load, sum); int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.max(skip, take);}
for (int n : new int[] {10, 20}) { int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; int best = tryAll(weight, fee, 50, 0, 0, 0); System.out.println(n + " parcels: " + best + " €, " + tries + " combinations");}10 parcels: 169 €, 1024 combinations20 parcels: 208 €, 1048576 combinationsEvery parcel doubles the combinations: 10 parcels give 1,024, 20 give over a million. With 30 parcels it is over a billion, and with 50 parcels it is 1,125,899,906,842,624. At a billion combinations a second that is about 13 days, and the courier leaves at eight in the morning.
The idea
A table of parcels × kilograms
The recursion keeps asking the same questions: "the best from parcel 7 onwards with 23 kg of room" comes up along many different paths. Memory on the pair (parcel, room) would stop the repeats. But here too the bottom-up table is simpler, and you already know it. Only this time a subproblem has two numbers: how many parcels you look at and how many kilograms of room you have. The table is two-dimensional.
The four things of the table:
- What a cell means. best[i][w] is the highest fee with the first i parcels and a load of at most w kg.
- Where it comes from. Either parcel i is not in, and then it is best[i − 1][w]. Or it is in: its fee plus best[i − 1][w − its weight], the best without it for the kilograms that are left. The cell keeps the larger.
- In what order it is filled. Row by row: each row reads only the row above.
- Where the answer is. At the bottom right: all parcels, the whole load. The start is row 0, with no parcels: 0 everywhere.
This is the knapsack problem (0/1 knapsack): things with a weight and a value, room with a limit, and each thing taken whole or not at all. It picks parcels for a run, tasks for a sprint with limited hours, ads for limited air time.
See it
Take or leave
The last run of the day: 6 kg of room are left in the box and four parcels are waiting. Watch the two cells every cell reads: the one above ("leave") and the arrow from the row above with the fee ("take"):
static List<Integer> pack(int[] weight, int[] fee, int cap) { int n = weight.length; int[][] best = new int[n + 1][cap + 1]; for (int i = 1; i <= n; i++) { int kg = weight[i - 1]; int paid = fee[i - 1]; for (int w = 0; w <= cap; w++) { best[i][w] = best[i - 1][w]; if (kg <= w) { int take = best[i - 1][w - kg] + paid; best[i][w] = Math.max(best[i][w], take); } } } List<Integer> taken = new ArrayList<>(); for (int i = n, w = cap; i > 0; i--) { if (best[i][w] != best[i - 1][w]) { taken.add(0, i); w -= weight[i - 1]; } } return taken;}Step by step, in words
- pack(weight, fee, 6): best[i][w] is the highest fee with the first i parcels and at most w kg. Row 0 has no parcels, so it is all zeros.
- Leave parcel i: the best stays what the row above had for the same kg, best[i − 1][w]. Parcel 1 weighs 4 kg, so below 4 kg that is all.
- Take parcel i: its fee plus the best of the row above for the kg that are left, best[i − 1][w − kg]. At 4 kg: 10 € + 0 = 10 € beats 0.
- Row 3, 6 kg: parcel 3 (3 kg, 6 €) plus the best for 3 kg without it, 7 €: 13 € > 10 €. Two cheaper parcels beat the priciest one per kg.
- Back from the bottom right corner: the same as above means the parcel was left, different means it was taken. Parcel 4 not taken, parcel 3 taken, parcel 2 taken, parcel 1 not taken: 2 + 3 = 13 €.
int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(pack(weight, fee, 6));[2, 3]The idea
Which parcels
The table says how much, and the courier needs to know which. The answer is in the table itself. You start at the bottom right corner. If the cell is the same as the one above, parcel i is not needed for it: you go one row up. If it is different, parcel i was taken: you go one row up and left by its weight. And so on down to row 0.
Today's 20 parcels and a box of 50 kg:
static int paid(int[] fee, List<Integer> taken) { int sum = 0; for (int p : taken) { sum += fee[p - 1]; } return sum;}
int[] weight = new int[20];int[] fee = new int[20];for (int i = 0; i < 20; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39;}List<Integer> taken = pack(weight, fee, 50);String list = taken.stream().map(String::valueOf).collect(Collectors.joining(" + "));System.out.println(list + ": " + paid(fee, taken) + " €");1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €The parcels weigh 48 kg and pay 208 €, the most of all the more than a million combinations. The table has 20 rows of parcels with 51 cells each, 1,020 cells in all.
Try it
Fill in
Parcel i goes in. How many kilograms are left for the other parcels?
static List<Integer> pack(int[] weight, int[] fee,
int cap) {
int n = weight.length;
int[][] best = new int[n + 1][cap + 1];
for (int i = 1; i <= n; i++) {
int kg = weight[i - 1];
int paid = fee[i - 1];
for (int w = 0; w <= cap; w++) {
best[i][w] = best[i - 1][w];
if (kg <= w) {
int take = best[i - 1][] + paid;
best[i][w] = Math.max(best[i][w], take);
}
}
}
List<Integer> taken = new ArrayList<>();
for (int i = n, w = cap; i > 0; i--) {
if (best[i][w] != best[i - 1][w]) {
taken.add(0, i);
w -= weight[i - 1];
}
}
return taken;
}The parcel takes kg of the w kilograms, so w - kg are left. The best for them without parcel i is in the row above, in the column w - kg, and it is already done.
The idea
Why not the priciest per kilogram
It looks sensible: you work out the fee per kilogram of every parcel and take the priciest that fits, then the next one. In the 6 kg run parcel 1 is 2.50 € per kilogram, parcel 2 is about 2.33, parcel 3 is 2, parcel 4 is 2.
static List<Integer> greedy(int[] weight, int[] fee, int cap) { boolean[] used = new boolean[weight.length]; List<Integer> taken = new ArrayList<>(); while (true) { int pick = -1; double rate = 0; for (int i = 0; i < weight.length; i++) { double perKg = (double) fee[i] / weight[i]; if (!used[i] && weight[i] <= cap && perKg > rate) { pick = i; rate = perKg; } } if (pick < 0) { return taken; } used[pick] = true; taken.add(pick + 1); cap -= weight[pick]; }}int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};List<Integer> fast = greedy(weight, fee, 6);List<Integer> best = pack(weight, fee, 6);String a = fast.stream().map(String::valueOf).collect(Collectors.joining(" + "));String b = best.stream().map(String::valueOf).collect(Collectors.joining(" + "));System.out.println("by €/kg: " + a + " = " + paid(fee, fast) + " €");System.out.println("table: " + b + " = " + paid(fee, best) + " €");by €/kg: 1 + 4 = 12 €table: 2 + 3 = 13 €Parcel 1 goes in first and takes 4 kg. 2 kg are left, and only parcel 4 fits in them. Parcels 2 and 3 would have filled the 6 kg completely and paid more. The rule chooses without looking back, and its first choice shuts out the better combination. The table tries both options for every parcel and every amount of room.
If parcels could be cut (sand, fuel), the priciest per kilogram first would be right. When a rule like that works and when it fails is the lesson "When greedy fails".
The idea
One row instead of a table
Each row reads only the row above. So you do not need the whole table: one row best[0..W] is enough, overwritten parcel after parcel. When only the total is needed, the program gets shorter:
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(bestFee(weight, fee, 6) + " €");13 €What matters is the direction: the kilograms go from the top down, from W to the weight of the parcel. Cell w reads best[w − weight], which is to its left. From the top down that cell has not been overwritten in this round yet, so it is from the row above, without the current parcel. That way the parcel goes in at most once.
Try it
Predict the output
5 kg of room and three parcels: 2 kg for 3 €, 3 kg for 4 €, 4 kg for 5 €. What does the program print?
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}
int[] weight = {2, 3, 4};int[] fee = {3, 4, 5};System.out.println(bestFee(weight, fee, 5) + " €");Parcels 1 and 2 weigh exactly 5 kg and pay 7 €. Parcel 3 is the priciest, but alone it pays 5 €, and with parcel 1 it makes 6 kg, which does not fit. 8 € is exactly that impossible pair.
Try it
Find the bug
A colleague turned the direction of the kilograms around. For the 6 kg run their program says:
int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(bestFee(weight, fee, 6) + " €");14 €And the best is 13 €. Which line has the bug?
Pick the line with the bug.
The kilograms go from the bottom up. When cell w reads best[w − weight], it has already been overwritten in the same round, with this parcel inside. So parcel 2 (3 kg, 7 €) goes into 3 kg, and then again into 6 kg: 7 + 7 = 14 €. From the top down the cell on the left is still from the previous round, and every parcel goes in at most once.
See it
Measure it: every combination against the table
We count the combinations checked and the "take or leave" comparisons in the row. The box is 50 kg. Above 20 parcels the combinations are not run: they are exactly 2ⁿ, so the estimate with "≈" is exact.
- Every combination
O(2ⁿ) - Table (up to 50 kg)
O(n)
| Algorithm | n = 10 | n = 20 | n = 30 | n = 40 |
|---|---|---|---|---|
| Every combination | 1,024 | 1,048,576 | ≈ 1,073,741,824 | ≈ 1,099,511,627,776 |
| Table (up to 50 kg) | 425 | 810 | 1,235 | 1,620 |
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}Every new parcel doubles the combinations, and adds one row to the table: at most 50 comparisons. At 40 parcels the table makes 1,620 comparisons, while the combinations are over a trillion. That is also why the table grows in a straight line: with a fixed 50 kg it is O(n). The price of W is in "More precisely" below.
More precisely, if you are curious
The same numbers in your language:
static long tries = 0;
static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) { if (i == weight.length) { tries++; return load <= cap ? sum : -1; } int skip = tryAll(weight, fee, cap, i + 1, load, sum); int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.max(skip, take);}
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { tries++; int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}
for (int n : new int[] {10, 20}) { int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; tryAll(weight, fee, 50, 0, 0, 0); long all = tries; tries = 0; bestFee(weight, fee, 50); System.out.println(n + " parcels: combinations " + all + ", table " + tries);}10 parcels: combinations 1024, table 42520 parcels: combinations 1048576, table 810Exercise
The run from the input
Solve it in your editor.
Run. Read the load in kg on the first line, the weights of the parcels on the second and the fees on the third. Print which parcels the courier should take and how much that pays. Use pack and paid from the lesson.
155 6 3 4 7 211 14 6 9 15 31 + 2 + 4: 34 €More tasks
- And how many kg. Also print how much the taken parcels weigh and how much room is left.
- Urgent parcels. Parcel 2 must go out no matter what. How do you fit that into the problem without writing a new table? (Hint: take it off the list and lower the load by its weight.)
- Two boxes. The bike has two boxes of 25 kg. Why is it not enough to solve the problem for 50 kg?
More precisely
More precisely: the price of W
Why "O(n · W)" does not mean "always fast".
More precisely, if you are curious
Pseudo-polynomial time. The table has n · W cells. n is how many parcels there are, but W is the value of the capacity, not how many things the input has. If the weights are in grams, the 50 kg box becomes W = 50,000 and the table is a thousand times bigger. If the capacity is a billion (bytes on a disk, cents in a budget), the table does not fit in memory, while the number of parcels is the same. A running time that is a polynomial in n and in the value of W, but not in the length of W in digits, is called pseudo-polynomial. Every extra digit in W multiplies the work by 10. That is why with huge W and few parcels, trying combinations with good pruning is sometimes faster.
Memory. The whole table is (n + 1) · (W + 1) numbers, one row is W + 1. But the row alone does not say which parcels: walking back needs all the rows, or at least one "taken" bit for every cell.
When parcels are unlimited. If there are as many of each kind as you like (crates of water at 6 kg, each for 4 €), from the top down is now wrong, and from the bottom up is exactly what you need: each kind can go in again. It is the same loop as in the change, where every coin can be used many times. The bug from "Find the bug" is the correct solution of a different problem.
Test