0/1 knapsack DP — the OilKnapsack bridge

◈ 6 cards

The dp[i][w] knapsack recurrence with reconstruction, pseudo-polynomial cost, and the same shape applied to the OilKnapsack project.

The 0/1 knapsack problem

$n$ items; item $i$ has weight $w_{i}$ and value $v_{i}$ . A knapsack holds capacity $W$ . Each item is taken whole or not at all (the 0/1 constraint). Maximize total value without exceeding $W$ .

Greedy by value-density $v_{i} / w_{i}$ fails here (you will see exactly why in Module 5) — a whole item you skip can leave wasted capacity. The fix is DP.

Optimal substructure & recurrence

Let $d p [i] [w]$ be the best value using only the first $i$ items within capacity $w$ . For item $i$ you either skip it or take it: $d p [i] [w] = {d p [i - 1] [w] max (d p [i - 1] [w], d p [i - 1] [w - w_{i}] + v_{i}) w_{i} > w w_{i} \leq w$ with base case $d p [0] [w] = 0$ . Fill the $(n + 1) \times (W + 1)$ table row by row.

Worked example: the CLRS counterexample

Items $(w, v)$ : $(10,\$60),(20,\$100),(30,\$120) $, c a p a c i t y$ W=50$. Greedy-by-density takes item 1 then item 2 for \$160; the DP finds items 2 + 3 = \$220. The table below prints the optimal value and reconstructs the chosen item indices.

Reconstruction

From $d p [n] [W]$ , walk up: if $d p [i] [w] \neq = d p [i - 1] [w]$ , item $i$ was taken — record it and drop $w$ by $w_{i}$ . Otherwise it was skipped. This is the same stored-choice idea as rod cutting and LCS.

Pseudo-polynomial cost — the trap

The table is $Θ (nW)$ . That is not polynomial in the input size: $W$ takes only $⌈ l g W ⌉$ bits to write down, so $nW$ is exponential in the bit-length of $W$ . We call this pseudo-polynomial. (0/1 knapsack is NP-complete; no truly polynomial algorithm is known.)

The OilKnapsack project — same shape, one twist

The AU final project, OilKnapsack, is this DP in disguise. The company will produce $P$ barrels. Order $i$ wants $q_{i}$ barrels for total price $p_{i}$ (which may be negative); each order is filled wholly or not at all. The company need not sell everything, but pays storage $s$ per unsold barrel. Maximize profit (which may be negative).

Map it: orders = items, barrels $q_{i}$ = weight, capacity = $P$ . The twist is the objective. Track $b es t [i] [b]$ = the best revenue selling exactly $b$ barrels using the first $i$ orders (or $- \infty$ if $b$ is unreachable). Then $profit = 0 \leq b \leq P max (b es t [n] [b] - s (P - b)),$ which charges storage on the $P - b$ unsold barrels and lets you stop short of selling all the oil. Because prices can be negative, the DP naturally skips unprofitable orders. The project rubric demands the full method: subproblems, recurrence, an acyclicity argument (each cell depends only on row $i - 1$ , so the dependency graph is a DAG), base cases, reconstruction, and an $O (n P)$ running-time analysis — exactly the pieces below.

The second exercise runs the OilKnapsack DP on a small instance with a negative-price order, printing the max profit and which orders to fill.

Three capacities of the dp table for the CLRS counterexample (W = 50). Read the highlighted cells bottom-up: dp[3][50] = 220 differs from dp[2][50] = 160, so item 3 is taken and capacity drops to 20; dp[2][20] = 100 differs from dp[1][20] = 60, so item 2 is taken and capacity drops to 0; dp[1][0] matches the row above, so item 1 is skipped. Chosen: items 2 and 3.

The final OilKnapsack row for P = 10, storage $2 per unsold barrel, orders (4, $40), (6, $50), (3, -$5), (5, $35). best is the revenue from selling exactly b barrels; empty cells are barrel counts no subset of orders can hit. Subtracting storage on the P - b unsold barrels turns revenue into profit, and the maximum over b is the answer — here b = 10 ($90, orders 1 and 2). Selling 9 nets only $73, which is why the storage term must be applied after the table, not inside it.