Modeling OilKnapsack as a DP

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(nP)$ 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 \text{ filled}} q_i \le 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 - (\text{barrels sold})$. So we make the barrels sold an explicit dimension. Let $$\textit{best}[i][b] = \text{maximum revenue achievable using only orders } 1\ldots i \text{ and selling } \textbf{exactly } b \text{ 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 \le i \le n$ and $0 \le b \le 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): $$\textit{best}[i][b] = \max\begin{cases} \textit{best}[i-1][b] & \text{(skip order } i) \\ \textit{best}[i-1][b - q_i] + p_i & \text{if } q_i \le b \text{ (fill order } i) \end{cases}$$ The "fill" branch is legal only when $q_i \le b$ (you can't sell $b$ barrels through this order if the order alone exceeds $b$) and when $\textit{best}[i-1][b-q_i] \ne -\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: $$\text{profit} = \max_{0 \le b \le P}\Big(\,\textit{best}[n][b] \;-\; s\,(P - b)\,\Big).$$ 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 $\textit{best}[i][b]$ depends only on row $i-1$ (entries $\textit{best}[i-1][b]$ and $\textit{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$: $$\textit{best}[0][0] = 0, \qquad \textit{best}[0][b] = -\infty \text{ for } b \ge 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 $\textit{best}[i][b] \ne \textit{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 $\Theta(nP)$ cells. The final storage scan over $b$ is $O(P)$ and the traceback is $O(n)$. Total: $O(nP)$, matching the bound the project demands. As with textbook knapsack this is pseudo-polynomial — $P$ is a *number*, written in $\lceil\lg P\rceil$ bits, so $nP$ 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 $= \text{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 = \mathbf{35}$ |

The optimum is profit $\$35$, filling orders $\{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.