Typical mistakes · In summary¶

18.4 Typical mistakes¶

Warning

Using row \(j-1\) in the second recurrence. The term \(p_j+v(j,k-w_j)\) refers to the same row \(j\): this is what allows several copies of item type \(j\).
Assuming that the capacity is filled. Part of the capacity may stay unused: when no item type fits, \(v(k)=0\), not \(-\infty\); in Example 18.1, \(v(1)=0\).
Reconstructing past the end. The reconstruction stops when the residual capacity is \(0\), or when \(s[k]=0\) in the first DP algorithm and \(j=0\) in the second one; otherwise it reads outside the arrays.
Forgetting the base case. \(v(0)=0\), and \(v[0..c]\) has \(c+1\) cells, not \(c\).

In summary

In the UKP an item type can be used any number of times, so the optimal value depends only on the residual capacity: \(v(k)=\max_{j:\,w_j\le k}\{p_j+v(k-w_j)\}\).
The first DP algorithm fills a vector of \(c+1\) cells in \(\Theta(nc)\) steps; the second one fills the matrix \(v(j,k)\) and reuses the same row for further copies.
An optimal solution is read backwards from the information stored, stopping when the residual capacity is zero or unused.
The running time is pseudo-polynomial, as for the KP.

Dashboard of the UKP example. Example 18.1 (\(c=7\), four item types):

Method	Lower bound	Upper bound	Origin
DP algorithm	\(14\)	\(14\)	optimal value, solution \((1,0,1,0)\)

Exercises on this chapter: Unbounded knapsack (UKP)