0/1 knapsack DP — the OilKnapsack bridge

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 $dp[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: $$dp[i][w] = \begin{cases} dp[i-1][w] & w_i > w \\ \max\big(dp[i-1][w],\; dp[i-1][w-w_i]+v_i\big) & w_i \le w \end{cases}$$ with base case $dp[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)$, capacity $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 $dp[n][W]$, walk up: if $dp[i][w] \ne dp[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 $\Theta(nW)$. That is not polynomial in the input *size*: $W$ takes only $\lceil\lg W\rceil$ 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 $best[i][b]$ = the best *revenue* selling exactly $b$ barrels using the first $i$ orders (or $-\infty$ if $b$ is unreachable). Then $$\text{profit} = \max_{0 \le b \le P}\big(best[n][b] - s\,(P-b)\big),$$ 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(nP)$ 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.