18.2 A first DP algorithm¶
Part 3 · Dynamic programming · Chapter 18 · Chapter 18: Unbounded knapsack (UKP) · Lecture notes, volume 3 (PDF) · Slides · Exercises: Unbounded knapsack (UKP) · App: DP tables for the knapsack problems
-
Step 1: computation of the optimal value
For any \(k \in \{0,1,\dots,c\}\), let \(v(k)\) be the optimal value of the UKP subinstance given by:
-
a knapsack of capacity \(k\),
-
the set \(\{1,2,\dots,n\}\) of \(n\) item types,
-
for each item type \(j \in \{1,2,\dots,n\}\), a profit \(p_j\) and a weight \(w_j\).
The recursive formula to compute \(v(k)\) reads as follows:
\[\begin{equation*} \label{eq:ukp1} v(k)= \left\{ \begin{array}{ll} 0, & \textrm{if $k=0$,}\\[1ex] \displaystyle \max_{j \,:\, w_j\le k}\{p_j+v(k-w_j)\}, & \textrm{if $k\ge 1$ and $w_j\le k$ for some $j$,}\\[2ex] 0, & \textrm{if $k\ge 1$ and $w_j> k$ for every $j$.} \end{array} \right. \tag{18.1} \end{equation*}\]-
The recursive decomposition process of formula \(\eqref{eq:ukp1}\) generates at most \(n\) independent subproblems, each corresponding to a possible choice of an item type \(j\), among those with \(w_j\le k\), to be inserted as one of the items of the knapsack of capacity \(k\).
-
The base case is \(v(0)=0\), since a knapsack of capacity \(0\) cannot contain any item and has profit \(0\). Moreover, if \(w_j>k\) for every item type \(j\), no item fits into the knapsack: the only feasible choice is to insert no item, and therefore \(v(k)=0\).
-
The optimal value \(v(k)\) is obtained by trying every item type \(j\) with \(w_j\le k\) and selecting the one that maximizes the sum \(p_j+v(k-w_j)\) of the profit of the chosen item type and the optimal value of the residual subproblem.
-
Since item type \(j\) is available in infinitely many copies, it may also be chosen again while solving the residual subproblem of capacity \(k-w_j\).
-
Hence, an optimal solution for a knapsack of capacity \(k\) is built by combining the chosen item type \(j\) with an optimal solution of the residual subproblem of capacity \(k-w_j\).
\(\rightsquigarrow\) Optimal Substructure verified!
-
Different choices of the first item type, possibly made for different values of \(k\), can lead to the same residual capacity, and therefore the same value \(v(k)\) may need to be computed several times during the recursive evaluation of formula \(\eqref{eq:ukp1}\).
\(\rightsquigarrow\) Overlapping Subproblems verified!
-
A first method to compute the optimal value \(v(c)\) of the UKP instance is the top-down approach.
-
The method starts from the call with \(k=c\) and evaluates formula \(\eqref{eq:ukp1}\) recursively: each call for a knapsack of capacity \(k\) triggers further calls for capacity \(k-w_j\), for every item type \(j\) with \(w_j\le k\), until the base case \(v(0)\) is reached or no item type fits into the residual capacity.
-
The recursion tree of the function \(v\) has one node for each recursive call, labeled with the function call it represents. The root represents the initial call. The children of a node represent the recursive calls made by that call. The leaf nodes represent the base cases.
Example 18.2: Recursion tree
We consider the UKP instance of Example 18.1, with capacity \(c=7\) and item types with weights \(w_1=2\), \(w_2=3\), \(w_3=5\), \(w_4=6\). This is the recursion tree of the top-down approach to compute \(v(7)\):
The function \(v\) is called \(15\) times, and the same subproblems are solved multiple times: \(v(2)\) is called \(3\) times, \(v(1)\) is called \(3\) times, and \(v(0)\) is called \(5\) times. All the other calls are made only once.
-
The value \(v(k)\), for a generic capacity \(k\), can be computed once the values \(v(k')\) are known for all smaller capacities \(k'<k\).
Example 18.3: Computing the values of the \(v\) function
We consider the UKP instance of Example 18.1 with a knapsack of capacity \(c=7\) and the following profits and weights:
\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 4 & 5 & 10 & 11 \\ {w_j} & 2 & 3 & 5 & 6 \\ \hline \end{array} \]The value of the function \(v\) can be computed by starting from the base case \(v(0)=0\) and then computing the values of \(v(1),v(2),\dots,v(7)\) in order, as follows:
-
Since no item type has \(w_j\le 1\), we have:
\[ v(1)=0. \] -
Once we have computed \(v(0)\), we can compute \(v(2)\), as follows:
\[ v(2)=p_1+v(0)=4+0=4. \] -
Once we have computed \(v(1)\) and \(v(0)\), we can compute \(v(3)\), as follows:
\[ v(3)=\max\{p_1+v(1),p_2+v(0)\}=\max\{4+0,5+0\}=5. \] -
Once we have computed \(v(2)\) and \(v(1)\), we can compute \(v(4)\), as follows:
\[ v(4)=\max\{p_1+v(2),p_2+v(1)\}=\max\{4+4,5+0\}=8. \] -
Once we have computed \(v(3)\), \(v(2)\) and \(v(0)\), we can compute \(v(5)\), as follows:
\[ v(5)=\max\{p_1+v(3),p_2+v(2),p_3+v(0)\}=\max\{4+5,5+4,10+0\}=10. \] -
Once we have computed \(v(4)\), \(v(3)\), \(v(1)\) and \(v(0)\), we can compute \(v(6)\), as follows:
\[\begin{align*} v(6)&=\max\{p_1+v(4),p_2+v(3),p_3+v(1),p_4+v(0)\}\\ &=\max\{4+8,5+5,10+0,11+0\}=12. \end{align*}\] -
Once we have computed \(v(5)\), \(v(4)\), \(v(2)\) and \(v(1)\), we can compute \(v(7)\), as follows:
\[\begin{align*} v(7)&=\max\{p_1+v(5),p_2+v(4),p_3+v(2),p_4+v(1)\}\\ &=\max\{4+10,5+8,10+4,11+0\}=14. \end{align*}\]
-
-
We can avoid solving the same subproblems repeatedly by storing the value of each subproblem as soon as it is computed. The values are stored in a lookup table.
-
Since solving a subproblem with value \(v(k)\) depends only on subproblems with values \(v(k')\), with \(k'<k\), we can solve the subproblems for increasing values of \(k\), starting from the base case \(v(0)=0\) and building up to \(v(c)\).
-
This observation naturally leads to a much more efficient method to compute the optimal value \(v(c)\) of the UKP instance.
-
A second method to compute the optimal value \(v(c)\) of the UKP instance is the bottom-up approach.
-
The method starts from the base case \(v(0)=0\) and evaluates formula \(\eqref{eq:ukp1}\) for increasing capacities \(k \in \{1,2,\dots,c\}\): each value \(v(k)\) is computed using the already-computed values \(v(0),v(1),\dots,v(k-1)\), until the value \(v(c)\) of the UKP instance is obtained.
This is the pseudo-code of the DP algorithm using the bottom-up approach:
Algorithm: UKP_DP1
Input: A UKP instance given by \(n\), arrays \(p[1..n]\), \(w[1..n]\), and capacity \(c\)Output: The optimal value of the UKP instance1Function UKP_DP1(\(n,p,w,c\))2\(v := \textnormal{new array}[0..c]\)3\(v[0] \leftarrow 0\)4for \(k := 1\) to \(c\) do5\(m := 0\)6for \(j := 1\) to \(n\) do7if \(w[j] \le k\) then8if \(p[j]+v[k-w[j]] > m\) then9\(m \leftarrow p[j]+v[k-w[j]]\)10end11end12end13\(v[k] \leftarrow m\)14end15return \(v[c]\)-
The vector \(v[0..c]\) is the lookup table: it stores the optimal values of all subproblems, with the base case \(v[0]=0\).
-
The outer loop, over \(k \in \{1,2,\dots,c\}\), computes \(v[k]\) in increasing order of capacity.
-
The inner loop, over \(j \in \{1,2,\dots,n\}\), examines every item type; the condition \(w[j]\le k\) checks whether item type \(j\) fits into capacity \(k\), and keeps in \(m\) the largest value \(p[j]+v[k-w[j]]\) found so far. If no item type fits, \(m\) remains equal to its initial value \(0\).
-
At the end of the inner loop, \(v[k] \leftarrow m\) stores the optimal value \(v[k]\).
-
Finally, the optimal value \(v[c]\) of the UKP instance is returned.
Example 18.4: Execution of the DP algorithm
We consider the UKP instance of Example 18.1 with a knapsack of capacity \(c=7\) and the following profits and weights:
\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 4 & 5 & 10 & 11 \\ {w_j} & 2 & 3 & 5 & 6 \\ \hline \end{array} \]For each step of the DP algorithm, the table shows the values of \(k\) and \(j\), the current value of \(m\), and the cell \(v[k]\). The cell of \(m\) is highlighted in red when updated; the cell of \(v[k]\) is highlighted in blue when assigned.
\(k\) \(j\) \(v[k]\) \(m\) Action \(-\) \(-\) 0 \(-\) \(v[0]\leftarrow 0\) \(-\) \(-\) 0 \(m := 0\) 1 1 \(-\) 0 \(w[1]=2>1\): skip 2 \(-\) 0 \(w[2]=3>1\): skip 3 \(-\) 0 \(w[3]=5>1\): skip 4 \(-\) 0 \(w[4]=6>1\): skip \(-\) 0 0 \(v[1]\leftarrow m=0\) \(-\) \(-\) 0 \(m := 0\) 2 1 \(-\) 4 \(p[1]{+}v[0]=4{+}0=4>m=0\): \(m\leftarrow 4\) 2 \(-\) 4 \(w[2]=3>2\): skip 3 \(-\) 4 \(w[3]=5>2\): skip 4 \(-\) 4 \(w[4]=6>2\): skip \(-\) 4 4 \(v[2]\leftarrow m=4\) \(-\) \(-\) 0 \(m := 0\) 3 1 \(-\) 4 \(p[1]{+}v[1]=4{+}0=4>m=0\): \(m\leftarrow 4\) 2 \(-\) 5 \(p[2]{+}v[0]=5{+}0=5>m=4\): \(m\leftarrow 5\) 3 \(-\) 5 \(w[3]=5>3\): skip 4 \(-\) 5 \(w[4]=6>3\): skip \(-\) 5 5 \(v[3]\leftarrow m=5\) \(-\) \(-\) 0 \(m := 0\) 4 1 \(-\) 8 \(p[1]{+}v[2]=4{+}4=8>m=0\): \(m\leftarrow 8\) 2 \(-\) 8 \(p[2]{+}v[1]=5{+}0=5\le m=8\): no update 3 \(-\) 8 \(w[3]=5>4\): skip 4 \(-\) 8 \(w[4]=6>4\): skip \(-\) 8 8 \(v[4]\leftarrow m=8\) \(-\) \(-\) 0 \(m := 0\) 5 1 \(-\) 9 \(p[1]{+}v[3]=4{+}5=9>m=0\): \(m\leftarrow 9\) 2 \(-\) 9 \(p[2]{+}v[2]=5{+}4=9=m\): no update 3 \(-\) 10 \(p[3]{+}v[0]=10{+}0=10>m=9\): \(m\leftarrow 10\) 4 \(-\) 10 \(w[4]=6>5\): skip \(-\) 10 10 \(v[5]\leftarrow m=10\) \(k\) \(j\) \(v[k]\) \(m\) Action \(-\) \(-\) 0 \(m := 0\) 6 1 \(-\) 12 \(p[1]{+}v[4]=4{+}8=12>m=0\): \(m\leftarrow 12\) 2 \(-\) 12 \(p[2]{+}v[3]=5{+}5=10\le m=12\): no update 3 \(-\) 12 \(p[3]{+}v[1]=10{+}0=10\le m=12\): no update 4 \(-\) 12 \(p[4]{+}v[0]=11{+}0=11\le m=12\): no update \(-\) 12 12 \(v[6]\leftarrow m=12\) \(-\) \(-\) 0 \(m := 0\) 7 1 \(-\) 14 \(p[1]{+}v[5]=4{+}10=14>m=0\): \(m\leftarrow 14\) 2 \(-\) 14 \(p[2]{+}v[4]=5{+}8=13\le m=14\): no update 3 \(-\) 14 \(p[3]{+}v[2]=10{+}4=14=m\): no update 4 \(-\) 14 \(p[4]{+}v[1]=11{+}0=11\le m=14\): no update \(-\) 14 14 \(v[7]\leftarrow m=14\) This is the vector \(v\) after the execution of the DP algorithm:
\[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {v[k]} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ \hline \end{array} \] -
-
After the execution of the DP algorithm, the vector \(v\) contains the optimal value \(v[k]\) for every capacity.
-
-
Step 2: computation of an optimal solution
-
To compute an optimal solution, it is necessary to store some additional information.
-
For each capacity \(k\), in addition to the optimal value \(v[k]\), we store \(s[k]\), the item type selected as first item in an optimal solution for a knapsack of capacity \(k\); if no item type fits into capacity \(k\), we set \(s[k]=0\).
-
Starting from \(k=c\), the value \(s[k]\) gives the item type of the first selected item; the residual capacity becomes \(k-w_{s[k]}\), and the same rule can be applied again, and so on, until the residual capacity reaches \(0\) or no item type fits into it (\(s[k]=0\)), in which case the residual capacity is left unused.
This is the pseudo-code of the DP algorithm using the bottom-up approach with the storing of the information necessary to compute an optimal solution:
Algorithm: UKP_DP1_InfoSol
Input: A UKP instance given by \(n\), arrays \(p[1..n]\), \(w[1..n]\), and capacity \(c\)Output: The optimal value of the UKP instance and the information vector \(s[0..c]\)1Function UKP_DP1_InfoSol(\(n,p,w,c\))2\(v := \textnormal{new array}[0..c]\); \(s := \textnormal{new array}[0..c]\)3\(v[0] \leftarrow 0\); \(s[0] \leftarrow 0\)4for \(k := 1\) to \(c\) do5\(m := 0\); \(t := 0\)6for \(j := 1\) to \(n\) do7if \(w[j] \le k\) then8if \(p[j]+v[k-w[j]] > m\) then9\(m \leftarrow p[j]+v[k-w[j]]\); \(t \leftarrow j\)10end11end12end13\(v[k] \leftarrow m\); \(s[k] \leftarrow t\)14end15return \(v[c],s\)-
The DP algorithm uses the additional temporary variable \(t\) to keep track of the decision made when \(m\) is updated. If item type \(j\) is selected, \(t\leftarrow j\) stores this decision; if no item type fits into capacity \(k\), \(t\) keeps its initial value \(0\).
-
At the end of the inner loop, \(s[k]\leftarrow t\) stores the selected item type, together with the optimal value \(v[k]\leftarrow m\).
Example 18.5: Computation of the additional information
We consider the UKP instance of Example 18.1 with a knapsack of capacity \(c=7\) and the following profits and weights:
\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 4 & 5 & 10 & 11 \\ {w_j} & 2 & 3 & 5 & 6 \\ \hline \end{array} \]For each step of the DP algorithm, the table shows the values of \(k\) and \(j\), the cell \(s[k]\), the current value of \(m\), and the current value of \(t\). The cell of \(m\) is highlighted in red when updated; the cell of \(t\) and the cell of \(s[k]\) are highlighted in blue when updated.
\(k\) \(j\) \(s[k]\) \(m\) \(t\) Action \(-\) \(-\) \(-\) \(-\) \(-\) Initial state: \(v[0]\leftarrow 0\), \(s[0]\leftarrow 0\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 1 1 \(-\) 0 0 \(w[1]=2>1\): skip 2 \(-\) 0 0 \(w[2]=3>1\): skip 3 \(-\) 0 0 \(w[3]=5>1\): skip 4 \(-\) 0 0 \(w[4]=6>1\): skip \(-\) 0 0 0 \(v[1]\leftarrow m=0\), \(s[1]\leftarrow t=0\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 2 1 \(-\) 4 1 \(4{+}0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\) 2 \(-\) 4 1 \(w[2]=3>2\): skip 3 \(-\) 4 1 \(w[3]=5>2\): skip 4 \(-\) 4 1 \(w[4]=6>2\): skip \(-\) 1 4 1 \(v[2]\leftarrow m=4\), \(s[2]\leftarrow t=1\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 3 1 \(-\) 4 1 \(4{+}0=4>m=0\): \(m\leftarrow 4\), \(t\leftarrow 1\) 2 \(-\) 5 2 \(5{+}0=5>m=4\): \(m\leftarrow 5\), \(t\leftarrow 2\) 3 \(-\) 5 2 \(w[3]=5>3\): skip 4 \(-\) 5 2 \(w[4]=6>3\): skip \(-\) 2 5 2 \(v[3]\leftarrow m=5\), \(s[3]\leftarrow t=2\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 4 1 \(-\) 8 1 \(4{+}4=8>m=0\): \(m\leftarrow 8\), \(t\leftarrow 1\) 2 \(-\) 8 1 \(5{+}0=5\le m=8\): no update 3 \(-\) 8 1 \(w[3]=5>4\): skip 4 \(-\) 8 1 \(w[4]=6>4\): skip \(-\) 1 8 1 \(v[4]\leftarrow m=8\), \(s[4]\leftarrow t=1\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 5 1 \(-\) 9 1 \(4{+}5=9>m=0\): \(m\leftarrow 9\), \(t\leftarrow 1\) 2 \(-\) 9 1 \(5{+}4=9=m\): no update 3 \(-\) 10 3 \(10{+}0=10>m=9\): \(m\leftarrow 10\), \(t\leftarrow 3\) 4 \(-\) 10 3 \(w[4]=6>5\): skip \(-\) 3 10 3 \(v[5]\leftarrow m=10\), \(s[5]\leftarrow t=3\) \(k\) \(j\) \(s[k]\) \(m\) \(t\) Action \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 6 1 \(-\) 12 1 \(4{+}8=12>m=0\): \(m\leftarrow 12\), \(t\leftarrow 1\) 2 \(-\) 12 1 \(5{+}5=10\le m=12\): no update 3 \(-\) 12 1 \(10{+}0=10\le m=12\): no update 4 \(-\) 12 1 \(11{+}0=11\le m=12\): no update \(-\) 1 12 1 \(v[6]\leftarrow m=12\), \(s[6]\leftarrow t=1\) \(-\) \(-\) 0 0 \(m := 0\), \(t := 0\) 7 1 \(-\) 14 1 \(4{+}10=14>m=0\): \(m\leftarrow 14\), \(t\leftarrow 1\) 2 \(-\) 14 1 \(5{+}8=13\le m=14\): no update 3 \(-\) 14 1 \(10{+}4=14=m\): no update 4 \(-\) 14 1 \(11{+}0=11\le m=14\): no update \(-\) 1 14 1 \(v[7]\leftarrow m=14\), \(s[7]\leftarrow t=1\) This is the vector \(s\) after the execution of the DP algorithm:
\[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 3 & 1 & 1 \\ \hline \end{array} \] -
-
Once the vector \(s\) has been computed, an optimal solution of the UKP instance can be computed by repeatedly applying the following rule, starting from \(k=c\) and \(x_j=0\) for all \(j \in \{1,2,\dots,n\}\):
\[ x_{s[k]} \leftarrow x_{s[k]}+1, \qquad k \leftarrow k-w_{s[k]}, \]until \(k=0\) or \(s[k]=0\). The second case occurs when no item type fits into the residual capacity \(k\), which is then left unused. This yields the vector \((x_1,x_2,\dots,x_n)\), where each entry \(x_j\) is the number of copies of item type \(j\) in an optimal solution.
-
The following pseudo-code implements the computation of an optimal solution, given the vector \(s\).
Algorithm: UKP_DP1_SolComputation
Input: The number \(n\) of item types, the capacity \(c\), the array \(w[1..n]\), and the vector \(s[0..c]\)Output: An optimal solution of the UKP instance1Function UKP_DP1_SolComputation(\(n,w,c,s\))2\(x := \textnormal{new array}[1..n]\)3for \(j := 1\) to \(n\) do4\(x[j] \leftarrow 0\)5end6\(k := c\)7while \(k > 0\) and \(s[k] > 0\) do8\(x[s[k]] \leftarrow x[s[k]]+1\)9\(k \leftarrow k - w[s[k]]\)10end11return \(x\)Example 18.6: Computing an optimal solution
After the execution of the DP algorithm on the instance of Example 18.1, we have the following vector \(s\):
\[ \begin{array}{c|cccccccc} \hline & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {s[k]} & 0 & 0 & 1 & 2 & 1 & 3 & 1 & 1 \\ \hline \end{array} \]We can compute an optimal solution for a knapsack of capacity \(c=7\) as follows:
Iteration \(k\) \(s[k]\) \(x[1]\) \(x[2]\) \(x[3]\) \(x[4]\) \(k \leftarrow k-w_{s[k]}\) \(-\) \(-\) \(-\) 0 0 0 0 \(k=7\) \(1\) \(7\) \(1\) 1 0 0 0 \(k=7-2=5\) \(2\) \(5\) \(3\) 1 0 1 0 \(k=5-5=0\) An optimal solution is the vector:
\[ (1,0,1,0) \]Its total weight is \(w_1+w_3=2+5=7=c\), and its total profit is \(p_1+p_3=4+10=14\), which matches the optimal value \(v(7)=14\).
-
18.2.1 Number of steps¶
-
Let \(S(n,c)\) denote the number of steps executed by
UKP_DP1in the worst case, where \(n\) is the number of item types and \(c\) is the knapsack capacity. We compute \(S(n,c)\) by counting how many times the lines of the pseudo-code ofUKP_DP1are executed. -
In the worst case, the conditions at lines 7 and 8 are true at every iteration of the inner loop, and therefore line 9 is executed as often as line 8. The number of executions of the relevant lines is:
-
Line 2 is executed \(1\) time.
-
Line 3 is executed \(1\) time.
-
Line 4 is executed \(c\) times.
-
Line 5 is executed \(c\) times.
-
Line 6 is executed \(cn\) times.
-
Line 7 is executed \(cn\) times.
-
Line 8 is executed \(cn\) times.
-
Line 9 is executed \(cn\) times.
-
Line 13 is executed \(c\) times.
-
Line 15 is executed \(1\) time.
Therefore, the total number of steps in the worst case is
\[ 1+1+c+c+cn+cn+cn+cn+c+1. \]Thus,
\[ S(n,c)=3+3c+4cn. \]Hence,
\[ S(n,c)=\Theta(nc). \]Indeed,
\[ \lim_{n,c\to\infty} \frac{4cn+3c+3}{nc} = \lim_{n,c\to\infty} \left(4+\frac{3}{n}+\frac{3}{nc}\right) = 4\in\mathbb{R}_{>0}. \]The DP algorithm executes
\[ S(n,c)=\Theta(nc) \]steps in the worst case.
-
-
The version
UKP_DP1_InfoSolstores the additional vector \(s\) and performs only a constant number of extra operations inside the same loops. Therefore, its number of steps remains \(\Theta(nc)\).