One problem, four techniques: the 0/1 knapsack
Greedy, dynamic programming, backtracking, branch and bound — the four design techniques from Abdul Bari's algorithms course, applied to the same instance so you can watch where each one wins and where it breaks. Then the same idea loading a trailer.
Every one of these runs in your browser on the instance below. Change nothing and the numbers are exact; the code is at the bottom in Java, the way I first wrote it.
The instance
Capacity 10. Four items, weight and value:
1 · Greedy
Sort by value-per-weight, take items in that order while they fit. It's the obvious move, it's fast, and for the fractional knapsack it's optimal. For 0/1 it isn't:
Greedy takes A (ratio 30) and B (25), reaches weight 6, and then nothing else fits. Value 160. The optimum is B + C = 220 — it skips the best-ratio item entirely. Greedy makes locally good choices it can never take back. That's the lesson of Bari's greedy section: it works exactly when the problem has the property that local optimality implies global (matroids, MST, Huffman), and 0/1 knapsack doesn't have it.
2 · Dynamic programming
Build a table: V[i][w] = best value using the first i items with capacity w. Each cell is max(V[i−1][w], V[i−1][w−wᵢ] + vᵢ) — skip the item, or take it and look up what was best with the remaining room. Fill it row by row:
The answer is the bottom-right cell. Walking back up the table (highlighted) recovers which items were taken. Cost is O(n·W) — pseudo-polynomial, which is why knapsack is NP-hard and yet solvable in practice when capacities are small integers. That's the "principle of optimality" from his DP lectures: an optimal solution contains optimal solutions to its sub-problems, so you can build up from the small ones and never recompute.
3 · Backtracking
Enumerate every subset as a binary tree — left branch takes the item, right branch skips it — but prune any branch whose weight has already exceeded capacity. Depth-first, so it finds a solution fast and keeps improving it:
Backtracking only prunes on feasibility: it abandons a branch when it's over capacity. It still explores every feasible subset, so it's exponential in the worst case. What it buys you over brute force is that infeasible subtrees never get expanded.
4 · Branch and bound
Same tree, one more weapon: an upper bound at every node. The bound here is the fractional-knapsack value of the remaining items — the best this subtree could possibly reach if you were allowed to take fractions. If that bound can't beat the best complete solution found so far, the subtree is pruned even though it's feasible:
Count the nodes. Branch and bound visited fewer, and the gap grows exponentially with problem size. The bound is where the engineering lives: tighter bound, smaller tree. A MILP solver — OR-Tools, Gurobi, CBC — is this tree with an LP relaxation as the bound, plus cutting planes to tighten it and heuristics to find good incumbents early. When I call a solver on a cutting-stock or scheduling model, this is what it's doing.
The same idea in a trailer
Truck cubing is knapsack with a second dimension and a floor. Pallets of different footprints and heights have to go into a 53-foot trailer; the objective is to fit as much as possible without leaving air you're paying to ship. This is a side view — length along the trailer, height up to the roof — packing pallets into shelves. Try the two orders:
The first strategy, next fit, places pallets in the order they arrived at the dock and starts a new shelf when one doesn't fit. The second, first-fit decreasing, sorts by height first and puts each pallet into the first shelf with room. FFD is still greedy — it can't undo a placement — but sorting makes it dramatically better, and it's provably within about 22% of optimal for 1-D bin packing. For a real load plan you'd add weight limits per axle, stacking rules, delivery-stop order, and a solver behind it when the heuristic isn't good enough; truck-cubing-bin-packing has those variants.
The Java
The four knapsack techniques, each a few lines. The visualizations above run the same logic in JavaScript.
// Greedy by ratio (optimal for fractional, not for 0/1)
static int greedy(int[] w, int[] v, int cap) {
Integer[] idx = new Integer[w.length];
for (int i = 0; i < w.length; i++) idx[i] = i;
Arrays.sort(idx, (a, b) -> Double.compare((double) v[b] / w[b], (double) v[a] / w[a]));
int used = 0, val = 0;
for (int i : idx) if (used + w[i] <= cap) { used += w[i]; val += v[i]; }
return val;
}
// Dynamic programming, O(n * cap)
static int dp(int[] w, int[] v, int cap) {
int[][] V = new int[w.length + 1][cap + 1];
for (int i = 1; i <= w.length; i++)
for (int c = 0; c <= cap; c++) {
V[i][c] = V[i - 1][c];
if (w[i - 1] <= c) V[i][c] = Math.max(V[i][c], V[i - 1][c - w[i - 1]] + v[i - 1]);
}
return V[w.length][cap];
}
// Backtracking: prune when over capacity
static int best;
static void backtrack(int[] w, int[] v, int cap, int i, int used, int val) {
if (used > cap) return; // infeasible: prune
best = Math.max(best, val);
if (i == w.length) return;
backtrack(w, v, cap, i + 1, used + w[i], val + v[i]); // take
backtrack(w, v, cap, i + 1, used, val); // skip
}
// Branch and bound: also prune when the fractional bound can't beat the incumbent
static double bound(int[] w, int[] v, int cap, int i, int used, int val) { // items sorted by ratio
double b = val; int room = cap - used;
for (; i < w.length && w[i] <= room; i++) { room -= w[i]; b += v[i]; }
if (i < w.length) b += (double) v[i] / w[i] * room; // fraction of the next item
return b;
}
static void branchAndBound(int[] w, int[] v, int cap, int i, int used, int val) {
if (used > cap) return;
best = Math.max(best, val);
if (i == w.length) return;
if (bound(w, v, cap, i, used, val) <= best) return; // can't win: prune
branchAndBound(w, v, cap, i + 1, used + w[i], val + v[i]);
branchAndBound(w, v, cap, i + 1, used, val);
}