Typical mistakes · In summary¶

17.4 Typical mistakes¶

Warning

Updating the single vector in increasing order of capacity. The cell \({v}[k-w_j]\) would already contain row \(j\), and item \(j\) could be selected more than once; the capacities are scanned from \(c\) downwards.
Forgetting the base cases. With no item available the optimal value is \(0\) for every capacity: \(v(0,k)=0\) for all \(k \in \{0,1,\dots,c\}\), not only for \(k=0\).
Reconstructing with the wrong index. At every step the item index decreases by one, while the capacity decreases by \(w_j\) only if item \(j\) is selected.
Calling \(\Theta(nc)\) polynomial. The capacity \(c\) is written with \(\log c\) digits, so the running time is exponential in the size of the input.
Reading \(u(n,q)\) as the optimal value. In the second DP algorithm \(u(n,q)\) is a minimum weight; the optimal value is the largest \(q\) with \(u(n,q)\le c\).

In summary

The recurrence \(v(j,k)\) chooses between leaving item \(j\) out and taking it; it has the optimal substructure and overlapping subproblems.
The matrix is filled bottom-up in \(\Theta(nc)\) steps; a single vector scanned downwards gives the optimal value with only \(c+1\) cells.
An optimal solution comes from the matrix \({s}\) of the decisions, read backwards from \((n,c)\).
The running time \(\Theta(nc)\) is pseudo-polynomial; the lists of non-dominated states store only the states that can be reached.
Exchanging profits and weights gives \(\Theta(nP)\) steps, which is better when the total profit \(P\) is small.

Dashboard of the KP example. Example 17.1 (\(c=5\), three items) with the bounds found so far:

Method	Lower bound	Upper bound	Origin
DP algorithm	\(14\)	\(14\)	optimal value, \(\Theta(nc)\) steps

Exercises on this chapter: 0/1 knapsack (KP)