Knapsack & DP / FPTAS

Pseudo-polynomial profit DP, then profit rounding for a fully polynomial approximation scheme.

The idea

In the 0/1 knapsack problem we are given $n$ items, item $j$ weighing $w_{j}$ and worth a profit $p_{j}$, and a capacity $W$. Choose a subset whose total weight is at most $W$ — each item taken whole or left behind — so that the total profit is as large as possible.

A dynamic program indexed by profit solves the problem exactly. For the first $j$ items and a profit target $P$, let $x(j, P)$ be the smallest total weight of a subset of those items whose profit is exactly $P$, and $\infty$ if none of them reaches $P$. Item $j$ is either left out, so the first $j-1$ items must supply $P$ themselves, or taken, so they must supply $P - p_{j}$ and its weight is added:

$x(j, P) = \min\{\, x(j-1, P),\ w_{j} + x(j-1, P - p_{j}) \,\}.$

Starting from $x(0, 0) = 0$, the table fills one row per item, and the answer is the largest profit $P$ with $x(n, P) \le W$.

Algorithm.

Algorithm: Profit-Indexed Knapsack DP Input: weights w_1, ..., w_n, profits p_1, ..., p_n, capacity W Output: the largest total profit of a subset of total weight ≤ W 1. x(0, 0) = 0; x(0, P) = ∞ for every P ≥ 1 // with no items, only profit 0 is reachable 2. j = 1 3. for every P from 0 to p_1 + ... + p_n: x(j, P) = min{ x(j-1, P), w_j + x(j-1, P - p_j) } // leave item j out, or take it; P - p_j < 0 gives ∞ 4. if j < n, set j = j + 1 and go to step 3 // one row per item 5. return the largest P with x(n, P) ≤ W

The table has a column for every profit up to $\sum_{j} p_{j}$, so the running time $O(n \sum_{j} p_{j})$ is pseudo-polynomial: polynomial in the profit values, but exponential in the number of bits that encode them. Rounding each profit down to $\lfloor p_{j}/K \rfloor$ for a scale factor $K$ chosen from a target accuracy $\varepsilon$ shrinks the table and yields a $(1 - \varepsilon)$-approximation in time polynomial in $n$ and $1/\varepsilon$ — a fully polynomial-time approximation scheme.

Algorithm.

Algorithm: Knapsack FPTAS Input: a knapsack instance, an accuracy ε with 0 < ε < 1 Output: a feasible subset with profit at least (1 - ε) × the optimum 1. K = ε × p_max / n // p_max = the largest profit; larger ε means coarser rounding 2. replace every profit p_j by ⌊p_j / K⌋ // each item forfeits less than K of true profit 3. run the profit-indexed DP on the rounded profits // original weights and capacity W 4. return the subset achieving the DP optimum // traced back through the table

Ways to work on it

• Walkthrough. The profit-indexed DP for 0/1 knapsack and why it is pseudo-polynomial.
• Practice. Round a profit by the FPTAS scale factor.
• Hardest. Choose the scale factor from the accuracy target and bound the approximation loss.

Not sure where to start? Take the ten-question placement test.