Implementing & analyzing OilKnapsack

From recurrence to code

Lesson 11.1 gave the model; now we implement it bottom-up and reconstruct which orders to fill — both are graded rubric lines ("construct a solution" and the report's results/screenshots), so neither can be skipped.

Step 3 (compute). Allocate a $(n+1) \times (P+1)$ table of $-\infty$, set $\textit{best}[0][0] = 0$, then fill row by row using the recurrence. The $-\infty$ sentinel marks *unreachable* sold-amounts; the "fill" branch is taken only when the order fits ($q_i \le b$) and the smaller amount $\textit{best}[i-1][b-q_i]$ is reachable.

The objective. After the table is full, scan $b = 0\ldots P$ and take $\max_b(\textit{best}[n][b] - s(P-b))$, remembering the winning $b^\*$.

Step 4 (reconstruct). From $b^\*$, walk $i = n \to 1$: order $i$ was filled exactly when its row changed the value ($\textit{best}[i][b] \ne \textit{best}[i-1][b]$); record it and drop $b$ by $q_i$.

Worked example

Produce $P = 10$ barrels, storage $s = \$2$ per unsold barrel. Orders $(q, p)$: $(4, \$40), (6, \$50), (3, -\$5), (5, \$35)$. Order 3 has a negative price, so a correct DP must *refuse* it. The best plan fills orders 1 and 2: that sells exactly $4 + 6 = 10$ barrels for $\$40 + \$50 = \$90$, with zero unsold barrels and thus no storage — profit $\$90$. Any plan that touches the $-\$5$ order, or leaves barrels unsold to pay storage, does worse. The first exercise below computes and reconstructs exactly this.

Analyzing it experimentally

The project report asks for a running-time-vs-input-size chart. Wall-clock timing is machine-dependent and noisy, so for a *reproducible* demonstration we count the DP table cells computed — each cell is $O(1)$ work, so the cell count is a faithful, deterministic stand-in for runtime. Hold $P$ fixed and double $n$: an $O(nP)$ algorithm must double the work each time, and the normalized ratio $\text{cells}/(nP)$ must stay flat. The second exercise prints this table — that flat ratio with doubling counts is your empirical confirmation of the $\Theta(nP)$ bound. (In your real report you would plot wall-clock seconds against $n$ for the screenshot; the *shape* is the same straight line.)