Implementing & analyzing OilKnapsack

◈ 5 cards

The full bottom-up OilKnapsack DP with order reconstruction, then an empirical scaling experiment that confirms the O(nP) bound — the two graded report pieces.

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 $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} \leq b$ ) and the smaller amount $best [i - 1] [b - q_{i}]$ is reachable.

The objective. After the table is full, scan $b = 0 \dots P$ and take $max_{b} (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 ( $best [i] [b] \neq = 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 (n P)$ algorithm must double the work each time, and the normalized ratio $cells / (n P)$ must stay flat. The second exercise prints this table — that flat ratio with doubling counts is your empirical confirmation of the $Θ (n P)$ bound. (In your real report you would plot wall-clock seconds against $n$ for the screenshot; the shape is the same straight line.)

The shape of the program. Nothing here is optional — the scan produces the graded profit and the traceback produces the graded order list.

The lesson’s own instance (P = 10, s = $2), restricted to the reachable sold-amounts — every other b is −∞. Accented cells are the traceback from b* = 10: rows 4 and 3 leave the value unchanged, so orders 4 and the −$5 order 3 were skipped; row 2 changes it (fill order 2, b → 4) and row 1 changes it again (fill order 1, b → 0). Profit = 90 − 2·0 = $90.

The exam trap in the last row: O(nP) looks polynomial because P looks like a count, but P is a *number* carried in about lg P bits, so nP is exponential in the length of the input. The bound is pseudo-polynomial.