DP for the multiple-choice knapsack problem¶

Part 3 · Dynamic programming · Chapter 21 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Multiple-choice knapsack (MCKP)

Prerequisites

From this module, the chapter «DP for the 0/1 knapsack problem»: the recurrence $v(j,k)$ of the 0/1 knapsack problem (KP) over items and capacities, the matrix $s$ of the decisions and the reconstruction of a solution.
From this module, the chapter «Knapsack problems»: the multiple-choice knapsack problem, its classes $\mathscr{J}_h$ and its feasibility condition.
From the module Algorithms: pseudocode conventions (Chapter 2) and the size of the input (Chapter 11).

Objectives

At the end of this chapter you will be able to:

write the recurrence $v(h,k)$ over the classes and the capacities, with the value $-\infty$ for the subinstances without a feasible solution;
run the DP algorithm by hand, trying every item of class $h$ that fits;
fill the matrix $s$ of the chosen items and reconstruct an optimal solution, one item per class;
count the $\Theta(nc)$ steps of the DP algorithm.

The problem of this chapter is the multiple-choice knapsack problem (MCKP): its definition and its assumptions are on its page.

21.1 A DP algorithm¶

Example 21.1: MCKP instance

We consider a knapsack of capacity $c=10$ and a set $\mathscr{I}=\{1,2,\dots,7\}$ of $7$ items ($n=7$), partitioned into $q=3$ classes: $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4,5\}$ and $\mathscr{J}_3=\{6,7\}$. The profits and weights are:

\[ \begin{array}{l|rr|rrr|rr} \hline & {j=1} & {j=2} & {j=3} & {j=4} & {j=5} & {j=6} & {j=7} \\ \hline {p_j} & 4 & 8 & 3 & 5 & 7 & 3 & 7 \\ {w_j} & 1 & 4 & 1 & 2 & 5 & 2 & 3 \\ \hline \end{array} \]

We refer to this MCKP instance as Example 21.1.

A feasible solution chooses exactly one item in each class, so it is described by the selected subset $S\subseteq\mathscr{I}$, with $|S\cap\mathscr{J}_h|=1$ for every class $h$, or by the binary vector $(x_1,x_2,\dots,x_n)$ of $S$.
The classes are the stages of the DP algorithm: class $h$ is decided after the classes $1,2,\dots,h-1$, and its decision is the item chosen in it.
Step 1: computation of the optimal value
For any $h \in \{0,1,\dots,q\}$ and $k \in \{0,1,\dots,c\}$, let $v(h,k)$ be the optimal value of the MCKP subinstance given by:
1. a knapsack of capacity $k$,
2. the classes $\mathscr{J}_1,\mathscr{J}_2,\dots,\mathscr{J}_h$,
3. for each item $j \in \mathscr{J}_1\cup\mathscr{J}_2\cup\dots\cup\mathscr{J}_h$, a profit $p_j$ and a weight $w_j$,
with $v(h,k)=-\infty$ if this subinstance has no feasible solution.

The recursive formula to compute $v(h,k)$ reads as follows:

\[\begin{equation*} \label{eq:mckp} v(h,k)= \left\{ \begin{array}{ll} 0 & \textrm{if $h=0$,}\\[2ex] -\infty & \begin{array}[t]{@{}l@{}}\textrm{if $h\ge 1$ and}\\ \textrm{$\forall j\in\mathscr{J}_h$: $w_j>k$,}\end{array}\\[4ex] \displaystyle \max_{j \in \mathscr{J}_h:\, w_j \le k} \big\{ p_j + v(h-1,k-w_j) \big\} & \begin{array}[t]{@{}l@{}}\textrm{if $h\ge 1$ and}\\ \textrm{$\exists j\in\mathscr{J}_h$: $w_j\le k$.}\end{array} \end{array} \right. \tag{21.1} \end{equation*}\]
- The value $-\infty$ follows the rules $p_j+(-\infty)=-\infty$ and $\max\{-\infty,a\}=a$: a subinstance without feasible solutions never gives a better value.
- The base cases are $v(0,k)=0$ for every $k$: with no class, the empty subset is feasible and has profit $0$, whatever the capacity.
- The formula $\eqref{eq:mckp}$ generates at most $|\mathscr{J}_h|$ independent subproblems, one for each item $j$ of class $h$ that fits in capacity $k$: the residual subproblem has the classes $1,2,\dots,h-1$ and the capacity $k-w_j$.
- Hence, an optimal solution for $(h,k)$ is built by combining the best item $j$ of class $h$ with an optimal solution of its residual subproblem.
  
  $\rightsquigarrow$ Optimal Substructure verified!
- Different choices in the classes $h+1,h+2,\dots,q$ can leave the same residual capacity, and therefore the same value $v(h,k)$ may be needed several times during the recursive evaluation of formula $\eqref{eq:mckp}$.
  
  $\rightsquigarrow$ Overlapping Subproblems verified!
- The value $v(h,k)$ depends only on values $v(h-1,k')$ with $k'< k$. Therefore, the bottom-up approach computes the rows $h=0,1,\dots,q$ in this order, each one for increasing $k$, and stores every value in a lookup table.
- The optimal value of the MCKP instance is $v(q,c)$, and the instance is infeasible if and only if $v(q,c)=-\infty$.

Step 2: computation of an optimal solution

For each class $h$ and capacity $k$, we store $s[h][k]$, the item of class $h$ chosen in an optimal solution of the subinstance $(h,k)$, that is, the item that maximizes the right-hand side of formula $\eqref{eq:mckp}$.
If $v[h][k]=-\infty$, no item is chosen and $s[h][k]=0$.

This is the pseudo-code of the DP algorithm using the bottom-up approach, which stores the matrix $s$ together with the matrix $v$:

Algorithm: MCKP_DP

Input: An MCKP instance given by $q$, the classes $\mathscr{J}_1,\dots,\mathscr{J}_q$, arrays $p[1..n]$, $w[1..n]$, and capacity $c$

Output: The optimal value of the MCKP instance and the matrix $s[0..q][0..c]$

1Function MCKP_DP($q,\mathscr{J},p,w,c$)

2$v := \textnormal{new array}[0..q][0..c]$; $s := \textnormal{new array}[0..q][0..c]$

3for $k := 0$ to $c$ do

4$v[0][k] \leftarrow 0$; $s[0][k] \leftarrow 0$

5end

6for $h := 1$ to $q$ do

7for $k := 0$ to $c$ do

8$m := -\infty$; $t := 0$

9for each $j \in \mathscr{J}_h$ do

10if $w[j]\le k$ and $p[j]+v[h-1][k-w[j]] > m$ then

11$m \leftarrow p[j]+v[h-1][k-w[j]]$; $t \leftarrow j$

12end

13end

14$v[h][k] \leftarrow m$; $s[h][k] \leftarrow t$

15end

16end

17return $v[q][c], s$

The variable $m$ starts from $-\infty$, not from $0$: exactly one item of class $h$ must be chosen, so the value of an empty choice is not available.
The innermost loop tries every item $j$ of class $h$ that fits, keeps in $m$ the largest value found so far, and in $t$ the item that gives it.
If no item of class $h$ gives a value larger than $-\infty$, the cell keeps $v[h][k]=-\infty$ and $s[h][k]=0$.
In case of ties the item met first in $\mathscr{J}_h$ is kept, because $m$ is updated only when the value is strictly larger.

Example 21.2: Execution of the DP algorithm

We consider the MCKP instance of Example 21.1, with capacity $c=10$ and classes $\mathscr{J}_1=\{1,2\}$, $\mathscr{J}_2=\{3,4,5\}$, $\mathscr{J}_3=\{6,7\}$.

For each step of the DP algorithm with $h\ge 1$, the table shows the values of $h$ and $k$, the cells $v[h][k]$ and $s[h][k]$, and the operation performed. The row $h=0$ is $v[0][k]=0$ and $s[0][k]=0$ for every $k$.

$h$	$k$	$v[h][k]$	$s[h][k]$	Action
$1$	$0$	$-\infty$	$0$	no item of $\mathscr{J}_1$ fits: $-\infty$
$1$	$1$	$4$	$1$	$\max\{p_1{+}v[0][0]\}=\max\{4\}=4$
$1$	$2$	$4$	$1$	$\max\{p_1{+}v[0][1]\}=\max\{4\}=4$
$1$	$3$	$4$	$1$	$\max\{p_1{+}v[0][2]\}=\max\{4\}=4$
$1$	$4$	$8$	$2$	$\max\{p_1{+}v[0][3],\,p_2{+}v[0][0]\}=\max\{4,8\}=8$
$1$	$5$	$8$	$2$	$\max\{p_1{+}v[0][4],\,p_2{+}v[0][1]\}=\max\{4,8\}=8$
$1$	$6$	$8$	$2$	$\max\{p_1{+}v[0][5],\,p_2{+}v[0][2]\}=\max\{4,8\}=8$
$1$	$7$	$8$	$2$	$\max\{p_1{+}v[0][6],\,p_2{+}v[0][3]\}=\max\{4,8\}=8$
$1$	$8$	$8$	$2$	$\max\{p_1{+}v[0][7],\,p_2{+}v[0][4]\}=\max\{4,8\}=8$
$1$	$9$	$8$	$2$	$\max\{p_1{+}v[0][8],\,p_2{+}v[0][5]\}=\max\{4,8\}=8$
$1$	$10$	$8$	$2$	$\max\{p_1{+}v[0][9],\,p_2{+}v[0][6]\}=\max\{4,8\}=8$
$2$	$0$	$-\infty$	$0$	no item of $\mathscr{J}_2$ fits: $-\infty$
$2$	$1$	$-\infty$	$0$	$\max\{p_3{+}v[1][0]\}=\max\{-\infty\}=-\infty$
$2$	$2$	$7$	$3$	$\max\{p_3{+}v[1][1],\,p_4{+}v[1][0]\}=\max\{7,-\infty\}=7$
$2$	$3$	$9$	$4$	$\max\{p_3{+}v[1][2],\,p_4{+}v[1][1]\}=\max\{7,9\}=9$
$2$	$4$	$9$	$4$	$\max\{p_3{+}v[1][3],\,p_4{+}v[1][2]\}=\max\{7,9\}=9$
$2$	$5$	$11$	$3$	$\max\{p_3{+}v[1][4],\,p_4{+}v[1][3],\,p_5{+}v[1][0]\}=\max\{11,9,-\infty\}=11$
$2$	$6$	$13$	$4$	$\max\{p_3{+}v[1][5],\,p_4{+}v[1][4],\,p_5{+}v[1][1]\}=\max\{11,13,11\}=13$
$2$	$7$	$13$	$4$	$\max\{p_3{+}v[1][6],\,p_4{+}v[1][5],\,p_5{+}v[1][2]\}=\max\{11,13,11\}=13$
$2$	$8$	$13$	$4$	$\max\{p_3{+}v[1][7],\,p_4{+}v[1][6],\,p_5{+}v[1][3]\}=\max\{11,13,11\}=13$
$2$	$9$	$15$	$5$	$\max\{p_3{+}v[1][8],\,p_4{+}v[1][7],\,p_5{+}v[1][4]\}=\max\{11,13,15\}=15$
$2$	$10$	$15$	$5$	$\max\{p_3{+}v[1][9],\,p_4{+}v[1][8],\,p_5{+}v[1][5]\}=\max\{11,13,15\}=15$

$h$	$k$	$v[h][k]$	$s[h][k]$	Action
$3$	$0$	$-\infty$	$0$	no item of $\mathscr{J}_3$ fits: $-\infty$
$3$	$1$	$-\infty$	$0$	no item of $\mathscr{J}_3$ fits: $-\infty$
$3$	$2$	$-\infty$	$0$	$\max\{p_6{+}v[2][0]\}=\max\{-\infty\}=-\infty$
$3$	$3$	$-\infty$	$0$	$\max\{p_6{+}v[2][1],\,p_7{+}v[2][0]\}=\max\{-\infty,-\infty\}=-\infty$
$3$	$4$	$10$	$6$	$\max\{p_6{+}v[2][2],\,p_7{+}v[2][1]\}=\max\{10,-\infty\}=10$
$3$	$5$	$14$	$7$	$\max\{p_6{+}v[2][3],\,p_7{+}v[2][2]\}=\max\{12,14\}=14$
$3$	$6$	$16$	$7$	$\max\{p_6{+}v[2][4],\,p_7{+}v[2][3]\}=\max\{12,16\}=16$
$3$	$7$	$16$	$7$	$\max\{p_6{+}v[2][5],\,p_7{+}v[2][4]\}=\max\{14,16\}=16$
$3$	$8$	$18$	$7$	$\max\{p_6{+}v[2][6],\,p_7{+}v[2][5]\}=\max\{16,18\}=18$
$3$	$9$	$20$	$7$	$\max\{p_6{+}v[2][7],\,p_7{+}v[2][6]\}=\max\{16,20\}=20$
$3$	$10$	$20$	$7$	$\max\{p_6{+}v[2][8],\,p_7{+}v[2][7]\}=\max\{16,20\}=20$

This is the matrix $v$ after the execution of the DP algorithm:

\[ \begin{array}{l|rrrrrrrrrrr} \hline {v[h][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {h=0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {h=1} & {-\infty} & {4} & {4} & {4} & {8} & {8} & {8} & {8} & {8} & {8} & {8} \\ {h=2} & {-\infty} & {-\infty} & {7} & {9} & {9} & {11} & {13} & {13} & {13} & {15} & {15} \\ {h=3} & {-\infty} & {-\infty} & {-\infty} & {-\infty} & {10} & {14} & {16} & {16} & {18} & {20} & {20} \\ \hline \end{array} \]

This is the matrix $s$ after the execution of the DP algorithm:

\[ \begin{array}{l|rrrrrrrrrrr} \hline {s[h][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {h=0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} & {0} \\ {h=1} & {0} & {1} & {1} & {1} & {2} & {2} & {2} & {2} & {2} & {2} & {2} \\ {h=2} & {0} & {0} & {3} & {4} & {4} & {3} & {4} & {4} & {4} & {5} & {5} \\ {h=3} & {0} & {0} & {0} & {0} & {6} & {7} & {7} & {7} & {7} & {7} & {7} \\ \hline \end{array} \]

For example, $v[2][1]=-\infty$: every choice of one item in $\mathscr{J}_1$ and one in $\mathscr{J}_2$ weighs at least $w_1+w_3=2$. The optimal value of the instance is $v[3][10]=20$, attained with item $s[3][10]=7$ of class $3$.

Once the matrix $s$ has been computed and $v[q][c]>-\infty$, an optimal solution is reconstructed by scanning the classes from $h=q$ down to $h=1$, starting from $k=c$ and $x_j=0$ for every item $j$:

\[ j \leftarrow s[h][k], \qquad x_j \leftarrow 1, \qquad k \leftarrow k - w_j. \]
Every class gives exactly one item, so the reconstruction selects $q$ items.

Algorithm: MCKP_Reconstruct

Input: The number $q$ of classes, the capacity $c$, the array $w[1..n]$, and the matrix $s[0..q][0..c]$, with $v[q][c]>-\infty$

Output: An optimal solution of the MCKP instance, as a binary vector

1Function MCKP_Reconstruct($q,c,w,s$)

2$x := \textnormal{new array}[1..n]$, with $x[j]=0$ for every $j$

3$k := c$

4for $h := q$ downto $1$ do

5$j \leftarrow s[h][k]$; $x[j] \leftarrow 1$

6$k \leftarrow k-w[j]$

7end

8return $x$

Example 21.3: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 21.1, we start from $h=3$ and $k=10$:

Iteration	$h$	$k$	$j=s[h][k]$	Selection	Capacity
$-$	$-$	$-$	$-$	$-$	$k=10$
$1$	$3$	$10$	$7$	$x[7]\leftarrow 1$	$k\leftarrow 10-3=7$
$2$	$2$	$7$	$4$	$x[4]\leftarrow 1$	$k\leftarrow 7-2=5$
$3$	$1$	$5$	$2$	$x[2]\leftarrow 1$	$k\leftarrow 5-4=1$

An optimal solution of the MCKP instance of Example 21.1 is $S=\{2,4,7\}$, that is, the vector $x=(0,1,0,1,0,0,1)$. Its total weight is $4+2+3=9\le c$ and its optimal value is $v(3,10)=20$.

21.1.1 Number of steps¶

Let $S(n,q,c)$ denote the number of steps executed by MCKP_DP in the worst case. The innermost loop runs over the items of class $h$, so over all the classes it runs $|\mathscr{J}_1|+|\mathscr{J}_2|+\dots+|\mathscr{J}_q|=n$ times for each capacity $k$. Assuming that the condition at line 10 is always true:
- Lines 2 and 17 are executed $1$ time each.
- Lines 3 and 4 are executed $c+1$ times each.
- Line 6 is executed $q$ times.
- Lines 7, 8 and 14 are executed $q(c+1)$ times each.
- Lines 9, 10 and 11 are executed $n(c+1)$ times each.
Therefore, the total number of steps in the worst case is

\[ S(n,q,c)=3n(c+1)+3q(c+1)+q+2c+4. \]

Since every class contains at least one item, $1\le q\le n$, and

\[ 3n(c+1)\;\le\; S(n,q,c)\;\le\; 6n(c+1)+n+2c+4. \]

Both bounds are $\Theta(nc)$, hence $S(n,q,c)=\Theta(nc)$.

The DP algorithm for the MCKP executes

\[ S(n,q,c)=\Theta\big(c\,(|\mathscr{J}_1|+|\mathscr{J}_2|+\dots+|\mathscr{J}_q|)\big)=\Theta(nc) \]

steps in the worst case.
The reconstruction executes $\Theta(q)$ steps, one for each class.

21.2 Typical mistakes¶

Warning

Starting $m$ from $0$ instead of $-\infty$. With $m=0$ a class with no item that fits would be skipped, and the solution would not contain exactly one item per class.
Adding the option «no item of class $h$». The term $v(h-1,k)$ of the KP recurrence has no place here: every class gives exactly one item.
Setting $v(0,k)=-\infty$ for $k\ge 1$. With no class the empty subset is feasible for every capacity: the capacity does not have to be filled.
Reconstructing an infeasible instance. If $v(q,c)=-\infty$ the instance has no feasible solution, and $s[q][c]=0$ gives no item to select.

21.3 In summary¶

In summary

The stages of the DP algorithm are the classes: $v(h,k)=\max_{j\in\mathscr{J}_h:\,w_j\le k}\{p_j+v(h-1,k-w_j)\}$, with $v(0,k)=0$.
The value $-\infty$ marks the subinstances without a feasible solution, and the instance is infeasible if and only if $v(q,c)=-\infty$.
The matrix $s$ stores the item chosen in each class, and an optimal solution is read backwards from $(q,c)$, one item per class.
The DP algorithm executes $\Theta(c\sum_{h=1}^{q}|\mathscr{J}_h|)=\Theta(nc)$ steps.

Dashboard of the MCKP example. Example 21.1 ($c=10$, three classes):

Method	Lower bound	Upper bound	Origin
DP algorithm	$20$	$20$	optimal value, solution $S=\{2,4,7\}$

Exercises on this chapter: Multiple-choice knapsack (MCKP)

\(h\)	\(k\)	\(v[h][k]\)	\(s[h][k]\)	Action
\(1\)	\(0\)	\(-\infty\)	\(0\)	no item of \(\mathscr{J}_1\) fits: \(-\infty\)
\(1\)	\(1\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][0]\}=\max\{4\}=4\)
\(1\)	\(2\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][1]\}=\max\{4\}=4\)
\(1\)	\(3\)	\(4\)	\(1\)	\(\max\{p_1{+}v[0][2]\}=\max\{4\}=4\)
\(1\)	\(4\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][3],\,p_2{+}v[0][0]\}=\max\{4,8\}=8\)
\(1\)	\(5\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][4],\,p_2{+}v[0][1]\}=\max\{4,8\}=8\)
\(1\)	\(6\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][5],\,p_2{+}v[0][2]\}=\max\{4,8\}=8\)
\(1\)	\(7\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][6],\,p_2{+}v[0][3]\}=\max\{4,8\}=8\)
\(1\)	\(8\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][7],\,p_2{+}v[0][4]\}=\max\{4,8\}=8\)
\(1\)	\(9\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][8],\,p_2{+}v[0][5]\}=\max\{4,8\}=8\)
\(1\)	\(10\)	\(8\)	\(2\)	\(\max\{p_1{+}v[0][9],\,p_2{+}v[0][6]\}=\max\{4,8\}=8\)
\(2\)	\(0\)	\(-\infty\)	\(0\)	no item of \(\mathscr{J}_2\) fits: \(-\infty\)
\(2\)	\(1\)	\(-\infty\)	\(0\)	\(\max\{p_3{+}v[1][0]\}=\max\{-\infty\}=-\infty\)
\(2\)	\(2\)	\(7\)	\(3\)	\(\max\{p_3{+}v[1][1],\,p_4{+}v[1][0]\}=\max\{7,-\infty\}=7\)
\(2\)	\(3\)	\(9\)	\(4\)	\(\max\{p_3{+}v[1][2],\,p_4{+}v[1][1]\}=\max\{7,9\}=9\)
\(2\)	\(4\)	\(9\)	\(4\)	\(\max\{p_3{+}v[1][3],\,p_4{+}v[1][2]\}=\max\{7,9\}=9\)
\(2\)	\(5\)	\(11\)	\(3\)	\(\max\{p_3{+}v[1][4],\,p_4{+}v[1][3],\,p_5{+}v[1][0]\}=\max\{11,9,-\infty\}=11\)
\(2\)	\(6\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][5],\,p_4{+}v[1][4],\,p_5{+}v[1][1]\}=\max\{11,13,11\}=13\)
\(2\)	\(7\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][6],\,p_4{+}v[1][5],\,p_5{+}v[1][2]\}=\max\{11,13,11\}=13\)
\(2\)	\(8\)	\(13\)	\(4\)	\(\max\{p_3{+}v[1][7],\,p_4{+}v[1][6],\,p_5{+}v[1][3]\}=\max\{11,13,11\}=13\)
\(2\)	\(9\)	\(15\)	\(5\)	\(\max\{p_3{+}v[1][8],\,p_4{+}v[1][7],\,p_5{+}v[1][4]\}=\max\{11,13,15\}=15\)
\(2\)	\(10\)	\(15\)	\(5\)	\(\max\{p_3{+}v[1][9],\,p_4{+}v[1][8],\,p_5{+}v[1][5]\}=\max\{11,13,15\}=15\)

\(h\)	\(k\)	\(v[h][k]\)	\(s[h][k]\)	Action
\(3\)	\(0\)	\(-\infty\)	\(0\)	no item of \(\mathscr{J}_3\) fits: \(-\infty\)
\(3\)	\(1\)	\(-\infty\)	\(0\)	no item of \(\mathscr{J}_3\) fits: \(-\infty\)
\(3\)	\(2\)	\(-\infty\)	\(0\)	\(\max\{p_6{+}v[2][0]\}=\max\{-\infty\}=-\infty\)
\(3\)	\(3\)	\(-\infty\)	\(0\)	\(\max\{p_6{+}v[2][1],\,p_7{+}v[2][0]\}=\max\{-\infty,-\infty\}=-\infty\)
\(3\)	\(4\)	\(10\)	\(6\)	\(\max\{p_6{+}v[2][2],\,p_7{+}v[2][1]\}=\max\{10,-\infty\}=10\)
\(3\)	\(5\)	\(14\)	\(7\)	\(\max\{p_6{+}v[2][3],\,p_7{+}v[2][2]\}=\max\{12,14\}=14\)
\(3\)	\(6\)	\(16\)	\(7\)	\(\max\{p_6{+}v[2][4],\,p_7{+}v[2][3]\}=\max\{12,16\}=16\)
\(3\)	\(7\)	\(16\)	\(7\)	\(\max\{p_6{+}v[2][5],\,p_7{+}v[2][4]\}=\max\{14,16\}=16\)
\(3\)	\(8\)	\(18\)	\(7\)	\(\max\{p_6{+}v[2][6],\,p_7{+}v[2][5]\}=\max\{16,18\}=18\)
\(3\)	\(9\)	\(20\)	\(7\)	\(\max\{p_6{+}v[2][7],\,p_7{+}v[2][6]\}=\max\{16,20\}=20\)
\(3\)	\(10\)	\(20\)	\(7\)	\(\max\{p_6{+}v[2][8],\,p_7{+}v[2][7]\}=\max\{16,20\}=20\)

Iteration	\(h\)	\(k\)	\(j=s[h][k]\)	Selection	Capacity
\(-\)	\(-\)	\(-\)	\(-\)	\(-\)	\(k=10\)
\(1\)	\(3\)	\(10\)	\(7\)	\(x[7]\leftarrow 1\)	\(k\leftarrow 10-3=7\)
\(2\)	\(2\)	\(7\)	\(4\)	\(x[4]\leftarrow 1\)	\(k\leftarrow 7-2=5\)
\(3\)	\(1\)	\(5\)	\(2\)	\(x[2]\leftarrow 1\)	\(k\leftarrow 5-4=1\)