18.3 A second 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 \(j \in \{0,1,\dots,n\}\) and \(k \in \{0,1,\dots,c\}\), let \(v(j,k)\) be the optimal value of the UKP subinstance given by:

  1. a knapsack of capacity \(k\),

  2. the set \(\{1,2,\dots,j\}\) of \(j\) item types,

  3. for each item type \(h \in \{1,2,\dots,j\}\), a profit \(p_h\) and a weight \(w_h\).

  The recursive formula to compute \(v(j,k)\) reads as follows:

  \[\begin{equation*} \label{eq:ukp2} v(j,k)= \left\{ \begin{array}{ll} 0, & \textrm{if $j=0$,}\\[1ex] v(j-1,k), & \textrm{if $j\ge 1$ and $k<w_j$,}\\[1ex] \max\{v(j-1,k),\ p_j+v(j,k-w_j)\}, & \textrm{if $j\ge 1$ and $k\ge w_j$.} \end{array} \right. \tag{18.2} \end{equation*}\]

  • The recursive decomposition process of formula \(\eqref{eq:ukp2}\) generates at most \(2\) independent subproblems, corresponding to whether or not to insert one copy of item type \(j\) into a knapsack of capacity \(k\), using only item types \(1,2,\dots,j\).

  • If \(w_j>k\), item type \(j\) cannot be inserted, and therefore the only feasible option is not to use it.

  • The base case is \(v(0,k)=0\) for every \(k\), since with no item type available the only feasible choice is to insert no item, which always has profit \(0\).

  • If \(j\ge 1\) and \(k\ge w_j\), the optimal value \(v(j,k)\) is obtained by trying the two possible options, not inserting item type \(j\) or inserting one further copy of it, and selecting the one that maximizes the profit. The corresponding values are \(v(j-1,k)\) and \(p_j+v(j,k-w_j)\), respectively.

  • If \(j\ge 1\) and \(k<w_j\), item type \(j\) cannot be used, and therefore \(v(j,k)=v(j-1,k)\).

  • The term \(p_j+v(j,k-w_j)\) refers to the same row \(j\), because after inserting one copy of item type \(j\), additional copies of the same item type are still available.

  • Hence, an optimal solution for a knapsack of capacity \(k\) using only item types \(1,2,\dots,j\) is built by combining the chosen decision on item type \(j\) with an optimal solution of the corresponding residual subproblem.

    \(\rightsquigarrow\) Optimal Substructure verified!

  • Different sequences of decisions on the item types, possibly made for different values of \(j\) and \(k\), can lead to the same subproblem, and therefore the same value \(v(j,k)\) may need to be computed several times during the recursive evaluation of formula \(\eqref{eq:ukp2}\).

    \(\rightsquigarrow\) Overlapping Subproblems verified!

  • A first method to compute the optimal value \(v(n,c)\) of the UKP instance is the top-down approach.

  • The method starts from the call with \((j,k)=(n,c)\) and evaluates formula \(\eqref{eq:ukp2}\) recursively: each call for capacity \(k\) using only item types \(1,2,\dots,j\) triggers further calls corresponding to the feasible decisions on item type \(j\), until one of the base cases \(v(0,k)\) is reached.

  • 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.7: 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(4,7)\):

    

    The function \(v\) is called \(32\) times, and the same subproblems are solved multiple times: \(v(1,1)\) is called \(3\) times, \(v(0,1)\) is called \(3\) times, \(v(1,2)\) is called \(2\) times, \(v(0,2)\) is called \(2\) times, \(v(1,0)\) is called \(2\) times, \(v(0,0)\) is called \(2\) times, and \(v(2,1)\) is called \(2\) times. All the other calls are made only once.

  • The value \(v(j,k)\) can be computed once \(v(j-1,k)\) is known and, when \(k\ge w_j\), \(v(j,k-w_j)\) is also known. Therefore, for a fixed value of \(j\), all values \(v(j,k)\) can be computed by considering the values of \(k\) in increasing order.

  • Starting from the base case \(v(0,k)=0\) for every \(k\), the values of the function \(v\) can be computed row by row, moving to the next value of \(j\) only after all values \(v(j,k)\) for the current value of \(j\) have been computed.

    Example 18.8: 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 values of the function \(v\) are computed as follows:

    • For \(j=1\), only item type \(1\) (\(w_1=2\)) is available. Therefore:

      \[ v(1,0)=0,\qquad v(1,1)=v(0,1)=0, \]
      \[ v(1,2)=\max\{v(0,2),p_1+v(1,0)\}=\max\{0,4+0\}=4, \]
      \[ v(1,3)=\max\{v(0,3),p_1+v(1,1)\}=\max\{0,4+0\}=4, \]
      \[ v(1,4)=\max\{v(0,4),p_1+v(1,2)\}=\max\{0,4+4\}=8, \]
      \[ v(1,5)=\max\{v(0,5),p_1+v(1,3)\}=\max\{0,4+4\}=8, \]
      \[ v(1,6)=\max\{v(0,6),p_1+v(1,4)\}=\max\{0,4+8\}=12, \]
      \[ v(1,7)=\max\{v(0,7),p_1+v(1,5)\}=\max\{0,4+8\}=12. \]

    • For \(j=2\), item types \(1\) and \(2\) are available. We obtain:

      \[ v(2,0)=0,\qquad v(2,1)=v(1,1)=0,\qquad v(2,2)=v(1,2)=4, \]
      \[ v(2,3)=\max\{v(1,3),p_2+v(2,0)\}=\max\{4,5+0\}=5, \]
      \[ v(2,4)=\max\{v(1,4),p_2+v(2,1)\}=\max\{8,5+0\}=8, \]
      \[ v(2,5)=\max\{v(1,5),p_2+v(2,2)\}=\max\{8,5+4\}=9, \]
      \[ v(2,6)=\max\{v(1,6),p_2+v(2,3)\}=\max\{12,5+5\}=12, \]
      \[ v(2,7)=\max\{v(1,7),p_2+v(2,4)\}=\max\{12,5+8\}=13. \]

    • For \(j=3\), item types \(1\), \(2\) and \(3\) are available. We obtain:

      \[ v(3,0)=0,\qquad v(3,1)=v(2,1)=0,\qquad v(3,2)=v(2,2)=4, \]
      \[ v(3,3)=v(2,3)=5,\qquad v(3,4)=v(2,4)=8, \]
      \[ v(3,5)=\max\{v(2,5),p_3+v(3,0)\}=\max\{9,10+0\}=10, \]
      \[ v(3,6)=\max\{v(2,6),p_3+v(3,1)\}=\max\{12,10+0\}=12, \]
      \[ v(3,7)=\max\{v(2,7),p_3+v(3,2)\}=\max\{13,10+4\}=14. \]

    • For \(j=4\), all item types are available. We obtain:

      \[ v(4,0)=0,\quad v(4,1)=v(3,1)=0,\quad v(4,2)=v(3,2)=4, \]
      \[ v(4,3)=v(3,3)=5,\quad v(4,4)=v(3,4)=8,\quad v(4,5)=v(3,5)=10, \]
      \[ v(4,6)=\max\{v(3,6),p_4+v(4,0)\}=\max\{12,11+0\}=12, \]
      \[ v(4,7)=\max\{v(3,7),p_4+v(4,1)\}=\max\{14,11+0\}=14. \]

  • 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 any particular subproblem depends only on subproblems with a smaller value of \(j\), or with the same value of \(j\) and a smaller capacity, we can solve the subproblems in increasing order of \(j\) and, for each fixed value of \(j\), in increasing order of capacity, starting from the base cases \(v(0,k)=0\) for every \(k \in \{0,1,\dots,c\}\) and building up to \(v(n,c)\).

  • This observation naturally leads to a much more efficient method to compute the optimal value \(v(n,c)\) of the UKP instance.

  • A second method to compute the optimal value \(v(n,c)\) of the UKP instance is the bottom-up approach.

  • The method starts from the base cases \(v(0,k)=0\) for every \(k \in \{0,1,\dots,c\}\) and evaluates formula \(\eqref{eq:ukp2}\) for increasing values of \(j \in \{1,2,\dots,n\}\) and \(k \in \{0,1,\dots,c\}\): each value \(v(j,k)\) is computed using already-computed values, until the value \(v(n,c)\) of the UKP instance is obtained.

    This is the pseudo-code of the DP algorithm using the bottom-up approach:

    Algorithm: UKP_DP2

    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

    1Function UKP_DP2(\(n,p,w,c\))

    2\(v := \textnormal{new array}[0..n][0..c]\)

    3for \(k := 0\) to \(c\) do

    4\(v[0][k] \leftarrow 0\)

    5end

    6for \(j := 1\) to \(n\) do

    7for \(k := 0\) to \(c\) do

    8if \(k < w[j]\) then

    9\(v[j][k] \leftarrow v[j-1][k]\)

    10else

    11if \(p[j]+v[j][k-w[j]] > v[j-1][k]\) then

    12\(v[j][k] \leftarrow p[j]+v[j][k-w[j]]\)

    13else

    14\(v[j][k] \leftarrow v[j-1][k]\)

    15end

    16end

    17end

    18end

    19return \(v[n][c]\)

    • The matrix \(v[0..n][0..c]\) is the lookup table: it stores the optimal values of all subproblems.

    • The initialization sets \(v[0][k]=0\) for every capacity \(k \in \{0,1,\dots,c\}\), since selecting no item is always feasible with profit \(0\).

    • The outer loop, over \(j \in \{1,2,\dots,n\}\), considers the available item types in increasing order.

    • The inner loop, over \(k \in \{0,1,\dots,c\}\), computes the best value for each capacity using only item types \(1,2,\dots,j\).

    • If \(k<w[j]\), item type \(j\) cannot be used, and therefore \(v[j][k] \leftarrow v[j-1][k]\).

    • Otherwise, the DP algorithm compares the value obtained by not using item type \(j\), namely \(v[j-1][k]\), with the value obtained by inserting one further copy of item type \(j\), namely \(p[j]+v[j][k-w[j]]\).

    • Finally, the optimal value of the UKP instance is returned as \(v[n][c]\).

    Example 18.9: 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 \(j\) and \(k\), the cell \(v[j][k]\), and the operation performed.

    \(j\)	\(k\)	\(v[j][k]\)	Action
    \(0\)	\(0\)	0	\(v[0][0]\leftarrow 0\)
    \(0\)	\(1\)	0	\(v[0][1]\leftarrow 0\)
    \(0\)	\(2\)	0	\(v[0][2]\leftarrow 0\)
    \(0\)	\(3\)	0	\(v[0][3]\leftarrow 0\)
    \(0\)	\(4\)	0	\(v[0][4]\leftarrow 0\)
    \(0\)	\(5\)	0	\(v[0][5]\leftarrow 0\)
    \(0\)	\(6\)	0	\(v[0][6]\leftarrow 0\)
    \(0\)	\(7\)	0	\(v[0][7]\leftarrow 0\)
    \(1\)	\(0\)	0	\(k=0<w[1]=2\): \(v[1][0]\leftarrow v[0][0]=0\)
    \(1\)	\(1\)	0	\(k=1<w[1]=2\): \(v[1][1]\leftarrow v[0][1]=0\)
    \(1\)	\(2\)	4	\(\max\{v[0][2],p[1]+v[1][0]\}=\max\{0,4+0\}=4\)
    \(1\)	\(3\)	4	\(\max\{v[0][3],p[1]+v[1][1]\}=\max\{0,4+0\}=4\)
    \(1\)	\(4\)	8	\(\max\{v[0][4],p[1]+v[1][2]\}=\max\{0,4+4\}=8\)
    \(1\)	\(5\)	8	\(\max\{v[0][5],p[1]+v[1][3]\}=\max\{0,4+4\}=8\)
    \(1\)	\(6\)	12	\(\max\{v[0][6],p[1]+v[1][4]\}=\max\{0,4+8\}=12\)
    \(1\)	\(7\)	12	\(\max\{v[0][7],p[1]+v[1][5]\}=\max\{0,4+8\}=12\)
    \(2\)	\(0\)	0	\(k=0<w[2]=3\): \(v[2][0]\leftarrow v[1][0]=0\)
    \(2\)	\(1\)	0	\(k=1<w[2]=3\): \(v[2][1]\leftarrow v[1][1]=0\)
    \(2\)	\(2\)	4	\(k=2<w[2]=3\): \(v[2][2]\leftarrow v[1][2]=4\)
    \(2\)	\(3\)	5	\(\max\{v[1][3],p[2]+v[2][0]\}=\max\{4,5+0\}=5\)
    \(2\)	\(4\)	8	\(\max\{v[1][4],p[2]+v[2][1]\}=\max\{8,5+0\}=8\)
    \(2\)	\(5\)	9	\(\max\{v[1][5],p[2]+v[2][2]\}=\max\{8,5+4\}=9\)
    \(2\)	\(6\)	12	\(\max\{v[1][6],p[2]+v[2][3]\}=\max\{12,5+5\}=12\)
    \(2\)	\(7\)	13	\(\max\{v[1][7],p[2]+v[2][4]\}=\max\{12,5+8\}=13\)

    \(j\)	\(k\)	\(v[j][k]\)	Action
    \(3\)	\(0\)	0	\(k=0<w[3]=5\): \(v[3][0]\leftarrow v[2][0]=0\)
    \(3\)	\(1\)	0	\(k=1<w[3]=5\): \(v[3][1]\leftarrow v[2][1]=0\)
    \(3\)	\(2\)	4	\(k=2<w[3]=5\): \(v[3][2]\leftarrow v[2][2]=4\)
    \(3\)	\(3\)	5	\(k=3<w[3]=5\): \(v[3][3]\leftarrow v[2][3]=5\)
    \(3\)	\(4\)	8	\(k=4<w[3]=5\): \(v[3][4]\leftarrow v[2][4]=8\)
    \(3\)	\(5\)	10	\(\max\{v[2][5],p[3]+v[3][0]\}=\max\{9,10+0\}=10\)
    \(3\)	\(6\)	12	\(\max\{v[2][6],p[3]+v[3][1]\}=\max\{12,10+0\}=12\)
    \(3\)	\(7\)	14	\(\max\{v[2][7],p[3]+v[3][2]\}=\max\{13,10+4\}=14\)
    \(4\)	\(0\)	0	\(k=0<w[4]=6\): \(v[4][0]\leftarrow v[3][0]=0\)
    \(4\)	\(1\)	0	\(k=1<w[4]=6\): \(v[4][1]\leftarrow v[3][1]=0\)
    \(4\)	\(2\)	4	\(k=2<w[4]=6\): \(v[4][2]\leftarrow v[3][2]=4\)
    \(4\)	\(3\)	5	\(k=3<w[4]=6\): \(v[4][3]\leftarrow v[3][3]=5\)
    \(4\)	\(4\)	8	\(k=4<w[4]=6\): \(v[4][4]\leftarrow v[3][4]=8\)
    \(4\)	\(5\)	10	\(k=5<w[4]=6\): \(v[4][5]\leftarrow v[3][5]=10\)
    \(4\)	\(6\)	12	\(\max\{v[3][6],p[4]+v[4][0]\}=\max\{12,11+0\}=12\)
    \(4\)	\(7\)	14	\(\max\{v[3][7],p[4]+v[4][1]\}=\max\{14,11+0\}=14\)

    This is the matrix \(v\) after the execution of the DP algorithm:

    \[ \begin{array}{l|rrrrrrrr} \hline {v[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 4 & 4 & 8 & 8 & 12 & 12 \\ {j=2} & 0 & 0 & 4 & 5 & 8 & 9 & 12 & 13 \\ {j=3} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ {j=4} & 0 & 0 & 4 & 5 & 8 & 10 & 12 & 14 \\ \hline \end{array} \]

  • After the execution of the DP algorithm, the matrix \(v\) contains the optimal value \(v[j][k]\) for every subproblem \((j,k)\).

• Step 2: computation of an optimal solution

  • To compute an optimal solution, it is necessary to store some additional information.

  • For each item type \(j\) and each capacity \(k\), in addition to the optimal value \(v[j][k]\), we store \(s[j][k]\), which is equal to \(1\) if one copy of item type \(j\) is used when computing \(v[j][k]\), and to \(0\) otherwise.

  • Starting from \(j=n\) and \(k=c\), if \(s[j][k]=0\), then item type \(j\) is not used and \(j\) is decreased by \(1\). If \(s[j][k]=1\), then one copy of item type \(j\) is used and the residual capacity becomes \(k-w_j\). The procedure stops when the residual capacity reaches \(0\) or when \(j=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_DP2_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 matrix of binary information \(s[0..n][0..c]\)

    1Function UKP_DP2_InfoSol(\(n,p,w,c\))

    2\(v := \textnormal{new array}[0..n][0..c]\); \(s := \textnormal{new array}[0..n][0..c]\)

    3for \(k := 0\) to \(c\) do

    4\(v[0][k] \leftarrow 0\); \(s[0][k] \leftarrow 0\)

    5end

    6for \(j := 1\) to \(n\) do

    7for \(k := 0\) to \(c\) do

    8if \(k < w[j]\) then

    9\(v[j][k] \leftarrow v[j-1][k]\); \(s[j][k] \leftarrow 0\)

    10else

    11if \(p[j]+v[j][k-w[j]] > v[j-1][k]\) then

    12\(v[j][k] \leftarrow p[j]+v[j][k-w[j]]\); \(s[j][k] \leftarrow 1\)

    13else

    14\(v[j][k] \leftarrow v[j-1][k]\); \(s[j][k] \leftarrow 0\)

    15end

    16end

    17end

    18end

    19return \(v[n][c],s\)

    • The DP algorithm uses the additional matrix \(s\), which keeps track of the decision made when \(v[j][k]\) is computed. If one copy of item type \(j\) is selected, \(s[j][k]\leftarrow 1\) stores this decision; otherwise, \(s[j][k]\leftarrow 0\) stores that item type \(j\) is not used.

    Example 18.10: 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 \(j\) and \(k\), the cell \(s[j][k]\), and the operation performed.

    \(j\)	\(k\)	\(s[j][k]\)	Action
    \(0\)	\(0\)	0	\(s[0][0]\leftarrow 0\)
    \(0\)	\(1\)	0	\(s[0][1]\leftarrow 0\)
    \(0\)	\(2\)	0	\(s[0][2]\leftarrow 0\)
    \(0\)	\(3\)	0	\(s[0][3]\leftarrow 0\)
    \(0\)	\(4\)	0	\(s[0][4]\leftarrow 0\)
    \(0\)	\(5\)	0	\(s[0][5]\leftarrow 0\)
    \(0\)	\(6\)	0	\(s[0][6]\leftarrow 0\)
    \(0\)	\(7\)	0	\(s[0][7]\leftarrow 0\)
    \(1\)	\(0\)	0	\(k<w[1]\): \(s[1][0]\leftarrow 0\)
    \(1\)	\(1\)	0	\(k<w[1]\): \(s[1][1]\leftarrow 0\)
    \(1\)	\(2\)	1	\(p[1]+v[1][0]=4+0>v[0][2]=0\): \(s[1][2]\leftarrow 1\)
    \(1\)	\(3\)	1	\(p[1]+v[1][1]=4+0>v[0][3]=0\): \(s[1][3]\leftarrow 1\)
    \(1\)	\(4\)	1	\(p[1]+v[1][2]=4+4>v[0][4]=0\): \(s[1][4]\leftarrow 1\)
    \(1\)	\(5\)	1	\(p[1]+v[1][3]=4+4>v[0][5]=0\): \(s[1][5]\leftarrow 1\)
    \(1\)	\(6\)	1	\(p[1]+v[1][4]=4+8>v[0][6]=0\): \(s[1][6]\leftarrow 1\)
    \(1\)	\(7\)	1	\(p[1]+v[1][5]=4+8>v[0][7]=0\): \(s[1][7]\leftarrow 1\)
    \(2\)	\(0\)	0	\(k<w[2]\): \(s[2][0]\leftarrow 0\)
    \(2\)	\(1\)	0	\(k<w[2]\): \(s[2][1]\leftarrow 0\)
    \(2\)	\(2\)	0	\(k<w[2]\): \(s[2][2]\leftarrow 0\)
    \(2\)	\(3\)	1	\(p[2]+v[2][0]=5+0>v[1][3]=4\): \(s[2][3]\leftarrow 1\)
    \(2\)	\(4\)	0	\(p[2]+v[2][1]=5+0\le v[1][4]=8\): \(s[2][4]\leftarrow 0\)
    \(2\)	\(5\)	1	\(p[2]+v[2][2]=5+4>v[1][5]=8\): \(s[2][5]\leftarrow 1\)
    \(2\)	\(6\)	0	\(p[2]+v[2][3]=5+5\le v[1][6]=12\): \(s[2][6]\leftarrow 0\)
    \(2\)	\(7\)	1	\(p[2]+v[2][4]=5+8>v[1][7]=12\): \(s[2][7]\leftarrow 1\)

    \(j\)	\(k\)	\(s[j][k]\)	Action
    \(3\)	\(0\)	0	\(k<w[3]\): \(s[3][0]\leftarrow 0\)
    \(3\)	\(1\)	0	\(k<w[3]\): \(s[3][1]\leftarrow 0\)
    \(3\)	\(2\)	0	\(k<w[3]\): \(s[3][2]\leftarrow 0\)
    \(3\)	\(3\)	0	\(k<w[3]\): \(s[3][3]\leftarrow 0\)
    \(3\)	\(4\)	0	\(k<w[3]\): \(s[3][4]\leftarrow 0\)
    \(3\)	\(5\)	1	\(p[3]+v[3][0]=10+0>v[2][5]=9\): \(s[3][5]\leftarrow 1\)
    \(3\)	\(6\)	0	\(p[3]+v[3][1]=10+0\le v[2][6]=12\): \(s[3][6]\leftarrow 0\)
    \(3\)	\(7\)	1	\(p[3]+v[3][2]=10+4>v[2][7]=13\): \(s[3][7]\leftarrow 1\)
    \(4\)	\(0\)	0	\(k<w[4]\): \(s[4][0]\leftarrow 0\)
    \(4\)	\(1\)	0	\(k<w[4]\): \(s[4][1]\leftarrow 0\)
    \(4\)	\(2\)	0	\(k<w[4]\): \(s[4][2]\leftarrow 0\)
    \(4\)	\(3\)	0	\(k<w[4]\): \(s[4][3]\leftarrow 0\)
    \(4\)	\(4\)	0	\(k<w[4]\): \(s[4][4]\leftarrow 0\)
    \(4\)	\(5\)	0	\(k<w[4]\): \(s[4][5]\leftarrow 0\)
    \(4\)	\(6\)	0	\(p[4]+v[4][0]=11+0\le v[3][6]=12\): \(s[4][6]\leftarrow 0\)
    \(4\)	\(7\)	0	\(p[4]+v[4][1]=11+0\le v[3][7]=14\): \(s[4][7]\leftarrow 0\)

    This is the matrix \(s\) after the execution of the DP algorithm:

    \[ \begin{array}{l|rrrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

  • Once the matrix \(s\) has been computed, an optimal solution for a knapsack of capacity \(c\) can be computed by repeatedly applying the following rule, starting from \((j,k)=(n,c)\) and \(x_h=0\) for all \(h \in \{1,2,\dots,n\}\):

    \[ \begin{array}{ll} j \leftarrow j-1 & \textrm{if $s[j][k]=0$,}\\[1ex] x_j \leftarrow x_j+1,\quad k \leftarrow k-w_j & \textrm{if $s[j][k]=1$.} \end{array} \]

    The procedure stops when \(k=0\) or \(j=0\); the second case occurs when the residual capacity is left unused. This yields the vector \((x_1,x_2,\dots,x_n)\), where each entry \(x_h\) is the number of copies of item type \(h\) in an optimal solution.

  • The following pseudo-code implements the computation of an optimal solution, given the matrix \(s\).

    Algorithm: UKP_DP2_SolComputation

    Input: The number of item types \(n\), the array \(w[1..n]\), the capacity \(c\), and the matrix \(s[0..n][0..c]\)

    Output: An optimal solution of the UKP instance

    1Function UKP_DP2_SolComputation(\(n,w,c,s\))

    2\(x := \textnormal{new array}[1..n]\)

    3for \(h := 1\) to \(n\) do

    4\(x[h] \leftarrow 0\)

    5end

    6\(j := n\)

    7\(k := c\)

    8while \(k > 0\) and \(j > 0\) do

    9if \(s[j][k] = 0\) then

    10\(j \leftarrow j-1\)

    11else

    12\(x[j] \leftarrow x[j]+1\)

    13\(k \leftarrow k-w[j]\)

    14end

    15end

    16return \(x\)

    Example 18.11: Computing an optimal solution

    After the execution of the DP algorithm on the instance of Example 18.1, we have the following matrix \(s\):

    \[ \begin{array}{l|rrrrrrrr} \hline {s[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} \\ \hline {j=0} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ {j=1} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ {j=2} & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ {j=3} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ {j=4} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \end{array} \]

    We can compute an optimal solution for a knapsack of capacity \(c=7\) as follows:

    Iteration	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	Action
    \(1\)	\(4\)	\(7\)	\(0\)	0	0	0	0	\(j\leftarrow 3\)
    \(2\)	\(3\)	\(7\)	\(1\)	0	0	1	0	\(x[3]\leftarrow 1\), \(k\leftarrow 7-5=2\)
    \(3\)	\(3\)	\(2\)	\(0\)	0	0	1	0	\(j\leftarrow 2\)
    \(4\)	\(2\)	\(2\)	\(0\)	0	0	1	0	\(j\leftarrow 1\)
    \(5\)	\(1\)	\(2\)	\(1\)	1	0	1	0	\(x[1]\leftarrow 1\), \(k\leftarrow 2-2=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(4,7)=14\).

18.3.1 Number of steps

• Let \(S(n,c)\) denote the number of steps executed by UKP_DP2 in 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 of UKP_DP2 are executed.

• In the worst case, line 11 is checked whenever the item type fits. Since the item weights are positive integers, this happens at most \(nc\) times. The number of executions of the relevant lines is:

  • Line 2 is executed \(1\) time.

  • Line 3 is executed \(c+1\) times.

  • Line 4 is executed \(c+1\) times.

  • Line 6 is executed \(n\) times.

  • Line 7 is executed \(n(c+1)\) times.

  • Line 8 is executed \(n(c+1)\) times.

  • Line 11 is executed at most \(nc\) times.

  • one among Line 9, Line 12, and Line 14 is executed for each pair \((j,k)\), and therefore these assignment lines are executed \(n(c+1)\) times in total.

  • Line 19 is executed \(1\) time.

  Therefore, the total number of steps in the worst case is

  \[ 1+(c+1)+(c+1)+n+n(c+1)+n(c+1)+nc+n(c+1)+1. \]

  Thus,

  \[ S(n,c)=4nc+4n+2c+4. \]

  Hence,

  \[ S(n,c)=\Theta(nc). \]

  Indeed,

  \[ \lim_{n,c\to\infty} \frac{4nc+4n+2c+4}{nc} = \lim_{n,c\to\infty} \left(4+\frac{4}{c}+\frac{2}{n}+\frac{4}{nc}\right) = 4\in\mathbb{R}_{>0}. \]

  The DP algorithm executes

  \[ S(n,c)=\Theta(nc) \]

  steps in the worst case.

• The version UKP_DP2_InfoSol stores the additional matrix \(s\) and performs only a constant number of extra operations inside the same loops. Therefore, its number of steps remains \(\Theta(nc)\).

---

Next: Typical mistakes · In summary