11.2 The knapsack problem

For the knapsack problem of the section on integer programming (values \(10, 13, 7, 8\), weights \(4, 6, 3, 5\), capacity \(10\)), take the items as stages and the remaining capacity as the state. With \(f_k(c)\) the best value using the first \(k\) items with capacity \(c\), \[ f_k(c) = \max \bigl \{f_{k - 1}(c),\ v_k + f_{k - 1}(c - w_k)\ \text {if } w_k \leq c\bigr \}, \qquad f_0(c) = 0 . \] The table has \((n + 1)(W + 1)\) entries, each found in constant time, so the problem is solved in \(O(nW)\) operations (Software 11.5.1). This is pseudo-polynomial: polynomial in the numerical value \(W\), not in the number of digits needed to write it, which is consistent with the knapsack problem being NP-hard. The last row of the table gives the optimum for every capacity at once, a sensitivity analysis for free.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.