Modeling OilKnapsack as a DP

◈ 5 cards

Recast the AU final project as 0/1 knapsack with a storage penalty, and answer the six rubric tasks: subproblems, recurrence, acyclicity, base cases, reconstruction, running time.

The project, restated

The AU final project (OilKnapsack, 20% of your grade) is graded entirely on the dynamic-programming method, so this lesson walks the six tasks the rubric names, one by one.

> An oil company will produce $P$ barrels this month. There are $n$ orders; order $i$ wants $q_{i}$ barrels for a total price $p_{i}$ (not per barrel) — and $p_{i}$ may be negative. Each order is filled wholly or not at all, and at most once. The company need not sell all its oil, but pays storage of $s$ dollars per unsold barrel. Choose which orders to fill to maximize profit (which itself may be negative). Design an $O (n P)$ algorithm.

First, recognize the shape. Orders are items, the barrels $q_{i}$ are an item's weight, and the production $P$ is the knapsack capacity — you cannot sell more than you produce, so $\sum_{i filled} q_{i} \leq P$ . This is 0/1 knapsack (whole-or-nothing items) with two twists the textbook version lacks: prices can be negative, and the objective subtracts a storage cost on whatever you do not sell.

Task 1 — Define the subproblems

The storage term depends on how many barrels stay unsold, which is $P - (barrels sold)$ . So we make the barrels sold an explicit dimension. Let $best [i] [b] = maximum revenue achievable using only orders 1 \dots i and selling exactly b barrels,$ or $- \infty$ if selling exactly $b$ barrels from the first $i$ orders is impossible. There are $(n + 1) (P + 1)$ such subproblems, indexed by $0 \leq i \leq n$ and $0 \leq b \leq P$ .

We deliberately track revenue at each sold-amount $b$ rather than folding storage in immediately, because the storage charge is a single end-of-month adjustment — we apply it once, at the very end, over all $b$ .

Task 2 — Relate the subproblems recursively

For order $i$ you make a binary choice: don't fill it (revenue and barrels unchanged) or fill it (gain $p_{i}$ revenue and $q_{i}$ barrels): $best [i] [b] = max {best [i - 1] [b] best [i - 1] [b - q_{i}] + p_{i} (skip order i) if q_{i} \leq b (fill order i)$ The "fill" branch is legal only when $q_{i} \leq b$ (you can't sell $b$ barrels through this order if the order alone exceeds $b$ ) and when $best [i - 1] [b - q_{i}] \neq = - \infty$ (the smaller amount must itself be reachable). Because $p_{i}$ may be negative, the $max$ will naturally skip an unprofitable order whenever skipping yields more revenue — no special case needed.

The final answer applies storage after the table is full: $profit = 0 \leq b \leq P max (best [n] [b] - s (P - b)) .$ This is where "need not sell all the oil" lives: we let $b$ range over every feasible sold-amount and pick the best after charging storage on the $P - b$ leftover barrels.

Task 3 — Argue the relation is acyclic

Every value $best [i] [b]$ depends only on row $i - 1$ (entries $best [i - 1] [b]$ and $best [i - 1] [b - q_{i}]$ ). Draw the subproblem graph with an edge from each cell to the cells it reads: all edges point from row $i$ strictly back to row $i - 1$ . A graph whose every edge decreases the row index can contain no cycle — the rows give a topological order. So the recurrence is acyclic and a bottom-up fill in order of increasing $i$ always finds its dependencies already computed. (This is the acyclicity argument the rubric asks for, stated explicitly.)

Task 4 — Provide base cases

The empty selection sells $0$ barrels for $\$0$: $best [0] [0] = 0, best [0] [b] = - \infty for b \geq 1.$ With no orders you cannot sell any barrels, so every sold-amount except $0$ is unreachable. The $- \infty$ sentinel is what makes the "need not fill the bag" semantics correct: unreachable sold-amounts never win the final $max$ .

Task 5 — Construct an optimal solution

The value table tells you how much profit; to report which orders to fill you trace back. Let $b *$ be the sold-amount that won the final $max$ . Walk $i$ from $n$ down to $1$ : if $best [i] [b] \neq = best [i - 1] [b]$ then order $i$ was filled (its row changed the value) — record it and set $b \leftarrow b - q_{i}$ . Otherwise it was skipped. This is the same stored-choice traceback as rod cutting and LCS, and it costs $O (n)$ .

Task 6 — Analyze the running time

Filling the table is two nested loops: $i$ from $1$ to $n$ , and $b$ from $0$ to $P$ , with $O (1)$ work per cell. That is $Θ (n P)$ cells. The final storage scan over $b$ is $O (P)$ and the traceback is $O (n)$ . Total: $O (n P)$ , matching the bound the project demands. As with textbook knapsack this is pseudo-polynomial — $P$ is a number, written in $⌈ l g P ⌉$ bits, so $n P$ is exponential in the input's bit-length.

A tiny worked instance

$P = 5$ barrels, storage $s = \$3$ per unsold barrel. Orders $(q, p) $:$ (3, \$20), (2, \$15), (4, \$25)$.

Enumerate feasible sold-amounts and their best revenue, then charge storage:

$b$ sold	best revenue	profit $= rev - 3 (5 - b)$
$0$	$0$	$0 - 15 = - 15$
$2$	$15$ (order 2)	$15 - 9 = 6$
$3$	$20$ (order 1)	$20 - 6 = 14$
$4$	$25$ (order 3)	$25 - 3 = 22$
$5$	$35$ (orders 1+2)	$35 - 0 = 35$

The optimum is profit $\$35 $, f i l l in g or d er s$ \{1, 2\}$ and selling all 5 barrels — storage is zero because nothing is left over. Lesson 11.2 computes exactly this with the bottom-up table.

Recognising the shape. The two accented rows are the only departures from textbook 0/1 knapsack — a value that may be negative, and a cost charged on what you *do not* take.

The whole recurrence on one card: base, skip, fill (legal only when the order fits and the smaller amount is reachable), then the final max over every b after charging storage once.