17.2.2 A first DP algorithm: An implementation with lists¶

Part 3 · Dynamic programming · Chapter 17 · Chapter 17: 0/1 knapsack (KP) · Lecture notes, volume 3 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: 0/1 knapsack (KP) · App: DP tables for the knapsack problems

Step 1: computation of the optimal value

The DP algorithm of this section stores one value for every pair given by an item and a capacity value, that is $(n+1)(c+1)$ values in total. Each row of the matrix ${v}$ is non-decreasing in the capacity value and changes only at a few capacity values: every other cell repeats the value of the cell on its left.
This subsection describes a different implementation of the same DP algorithm. The recursive decomposition and the optimal substructure are the ones of formula $\eqref{eq:1}$: what changes is the data structure.
Instead of a whole row of the matrix, only the pairs at which the row changes are stored, that is only the pairs that are actually obtained by a subset of items. These pairs are kept in a list, one list for each item.

A state is a pair $(w,p)$, where $w$ is the total weight and $p$ is the total profit of a subset of items whose total weight does not exceed the knapsack capacity $c$.

The empty subset gives the state $(0,0)$. A subset of the items $\{1,2,\dots,j\}$ gives a state obtained by summing the weights and the profits of its items.
Two different subsets can give the same state. In this case the two subsets are interchangeable: both occupy the same weight in the knapsack and both give the same profit, and therefore it is enough to keep one state.
More generally, a state can be discarded whenever another state is at least as good in both components.

Given two states $(w,p)$ and $(w',p')$ with $(w,p)\ne(w',p')$, the state $(w,p)$ dominates the state $(w',p')$ if

\[ w\le w' \qquad \textrm{and} \qquad p\ge p'. \]

A state is non-dominated if no other state dominates it.
A dominated state can be discarded. Indeed, let $(w,p)$ dominate $(w',p')$ and let $S'$ be a subset of the remaining items that can be added to $(w',p')$ without exceeding the capacity.
Since $w\le w'$, the same subset $S'$ can also be added to $(w,p)$, and since $p\ge p'$ the resulting total profit is not smaller. Therefore no optimal solution is lost.
For any $j \in \{0,1,\dots,n\}$, let $L_j$ be the list of the non-dominated states of the KP subinstance given by:
1. a knapsack of capacity $c$,
2. a set $\{1,2,\dots,j\}$ of available items,
3. for each item $h \in \{1,2,\dots,j\}$, a profit $p_h$ and a weight $w_h$.
The states of $L_j$ are sorted by strictly increasing weight.

The recursive formula to compute $L_j$ reads as follows:

\[\begin{equation*} \label{eq:4} L_j= \left\{ \begin{array}{ll} \big\{(0,0)\big\} & \textrm{if $j=0$,}\\[2ex] \textrm{nd}\big(L_{j-1}\cup M_j\big) & \textrm{if $1\le j \le n$,} \end{array} \right. \tag{17.2} \end{equation*}\]

where $\textrm{nd}(S)$ denotes the list of the non-dominated states of a set $S$ of states, and

\[ M_j=\big\{\,(w+w_j,\;p+p_j)\;:\;(w,p)\in L_{j-1},\ w+w_j\le c\,\big\}. \]
The recursive decomposition process of formula $\eqref{eq:4}$ generates at most $2$ independent subproblems for each state of $L_{j-1}$, corresponding to whether or not to select item $j$. If item $j$ is not selected, the state is unchanged and belongs to $L_{j-1}$. If item $j$ is selected, the state becomes $(w+w_j,p+p_j)$ and belongs to $M_j$; this option is available only when $w+w_j\le c$.
Here, $L_0=\{(0,0)\}$ since the only subset of an empty set of items is the empty subset.
Hence, every non-dominated state reachable with the items $\{1,2,\dots,j\}$ is built by combining the chosen decision on item $j$ with a non-dominated state reachable with the items $\{1,2,\dots,j-1\}$.

$\rightsquigarrow$ Optimal Substructure verified!
Different subsets of the items $\{1,2,\dots,j\}$ can give the same state, and a state can also be dominated by another one. In both cases a single state is kept in $L_j$, and all the subsets that lead to it are treated at once in the following iterations.

$\rightsquigarrow$ Overlapping Subproblems verified!
The optimal value of the KP instance is the largest profit stored in the last list.

The optimal value of the KP instance is

\[\begin{equation*} \label{eq:5} \max \big\{\, p \;:\; (w,p)\in L_n \,\big\}. \tag{17.3} \end{equation*}\]
In a list of non-dominated states sorted by strictly increasing weight, the profits are also strictly increasing: if a state had a weight larger than another one and a profit not larger, it would be dominated. Therefore the maximum of formula $\eqref{eq:5}$ is the profit of the last state of $L_n$.
The list $L_j$ holds the information of the row $j$ of the matrix ${v}$ in compressed form:

\[ {v}[j][k]=\max\big\{\,p \;:\; (w,p)\in L_j,\ w\le k\,\big\} \qquad \forall k \in \{0,1,\dots,c\}. \]

Every state $(w,p)$ of $L_j$ is a capacity value at which the row increases, and $p$ is the new value.

Example 17.9: The lists of states

We consider the KP instance of Example 17.1 with a knapsack of capacity $c=5$ and the following profits and weights:

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

Each shaded band collects the states of one list. An arc entering the band of $L_j$ corresponds to the decision taken on item $j$: a horizontal arc means that item $j$ is not selected, while a slanted arc means that item $j$ is selected. The thick arcs give the states of an optimal solution.

The two crossed states of the last band are dominated and are therefore discarded: $(3,7)$ is dominated by $(3,8)$ and $(5,13)$ is dominated by $(5,14)$. Selecting item $3$ from the states $(3,7)$ and $(5,13)$ of $L_2$ would give the total weights $6$ and $8$, which exceed the knapsack capacity $c=5$, and therefore no arc leaves these two states towards the states of $M_3$.
The lists are computed for increasing values of $j \in \{1,2,\dots,n\}$, starting from $L_0=\{(0,0)\}$: each list $L_j$ is computed from the already-computed list $L_{j-1}$, until the list $L_n$ is obtained.
The list $L_{j-1}$ and the list $M_j$ are both sorted by increasing weight, because $M_j$ is obtained from $L_{j-1}$ by adding the same weight $w_j$ to every state. Therefore the union of formula $\eqref{eq:4}$ is computed by scanning the two lists at the same time, as in the merge of two sorted lists.

To describe the scanning order we use the following convention.

The state $(w,p)$ precedes the state $(w',p')$ if

\[ w<w' \qquad \textrm{or} \qquad \textrm{($w=w'$ and $p>p'$)}. \]

If the states are scanned in this order, a state is non-dominated if and only if its profit is strictly larger than the largest profit of the states already scanned. Indeed, every state already scanned has a weight not larger, and therefore it dominates the current state as soon as its profit is not smaller.

This is the pseudo-code of the DP algorithm using lists:

Algorithm: DP_Lists

Input: A KP instance given by the number $n$ of items, arrays $p[1..n]$ and $w[1..n]$ of item profits and weights, and the knapsack capacity $c$

Output: The optimal value of the KP instance

1Function DP_Lists($n,p,w,c$)

2$L := \textnormal{new list containing the single state } (0,0)$

3for $j := 1$ to $n$ do

4$M := \textnormal{new empty list}$

5for $h := 1$ to $|L|$ do

6if $L[h].w + w[j] \le c$ then

7append $(L[h].w + w[j],</div><div class="pc" style="--liv:4" id="box-34-kplist-f"><span class="pc-n">8</span>L[h].p + p[j])<span class="arithmatex">\(to$</span>M\)

9end

10end

11$L \leftarrow \textnormal{\tt Merge}(L,M)$

12end

13return $L[|L|].p$

This is the pseudo-code of the procedure that merges two lists and discards the dominated states:

Algorithm: Merge

Input: Two lists $L$ and $M$ of states, both sorted by increasing weight

Output: The list of the non-dominated states of $L\cup M$, sorted by increasing weight

1Function Merge($L,M$)

2$R := \textnormal{new empty list}$

3$h := 1$

4$k := 1$

5$\pi := -1$

6while $h \le |L|$ or $k \le |M|$ do

7if $k>|M|$ or ($h\le |L|$ and $L[h]$ precedes $M[k]$) then

8$(a,b) \leftarrow L[h]$

9$h \leftarrow h+1$

10else

11$(a,b) \leftarrow M[k]$

12$k \leftarrow k+1$

13end

14if $b > \pi$ then

15append $(a,b)$ to $R$

16$\pi \leftarrow b$

17end

18end

19return $R$

The list $L$ is the lookup table: at the end of the iteration for item $j$, it stores the list $L_j$.
The list $L$ is initialized with the single state $(0,0)$, which is the list $L_0$.
The outer loop, over items $j \in \{1,2,\dots,n\}$, computes one list for each item.
The inner loop builds the list $M$ of the states obtained by selecting item $j$. A state is added to $M$ only when the resulting total weight does not exceed the knapsack capacity.
The procedure Merge scans the two lists at the same time and keeps a state only when its profit is strictly larger than the largest profit already appended, which is stored in the auxiliary variable $\pi$. The initial value $\pi=-1$ guarantees that the first scanned state is always appended.
Since the states of $L$ are sorted by strictly increasing weight and strictly increasing profit, the largest profit is the one of the last state. Therefore the optimal value of the KP instance is returned as $L[|L|].p$.

Example 17.10: Execution of the DP algorithm

We consider the KP instance of Example 17.1 with a knapsack of capacity $c=5$ and the following profits and weights:

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

For each item $j$, the table shows the list $M_j$ of the states obtained by selecting item $j$ and the resulting list $L_j$.

\[ \begin{array}{c|l|l} \hline {j} & {M_j} & {L_j} \\ \hline {0} & {-} & {\{(0,0)\}} \\ {1} & {\{(2,6)\}} & {\{(0,0),(2,6)\}} \\ {2} & {\{(3,7),(5,13)\}} & {\{(0,0),(2,6),(3,7),(5,13)\}} \\ {3} & {\{(3,8),(5,14)\}} & {\{(0,0),(2,6),(3,8),(5,14)\}} \\ \hline \end{array} \]

For each state scanned by Merge, the table shows the value of $j$, the state, the list it is taken from, and the operation performed.

$j$	state	from	Action
$1$	$(0,0)$	$L_{0}$	$0>\pi=-1$: append
$1$	$(2,6)$	$M_1$	$6>\pi=0$: append
$2$	$(0,0)$	$L_{1}$	$0>\pi=-1$: append
$2$	$(2,6)$	$L_{1}$	$6>\pi=0$: append
$2$	$(3,7)$	$M_2$	$7>\pi=6$: append
$2$	$(5,13)$	$M_2$	$13>\pi=7$: append
$3$	$(0,0)$	$L_{2}$	$0>\pi=-1$: append
$3$	$(2,6)$	$L_{2}$	$6>\pi=0$: append
$3$	$(3,8)$	$M_3$	$8>\pi=6$: append
$3$	$(3,7)$	$L_{2}$	$7\le\pi=8$: discard (dominated)
$3$	$(5,14)$	$M_3$	$14>\pi=8$: append
$3$	$(5,13)$	$L_{2}$	$13\le\pi=14$: discard (dominated)

The last state of $L_3$ is $(5,14)$, and therefore the optimal value of the KP instance is $14$.

After the execution of the DP algorithm, the list $L$ contains the non-dominated states $L_n$ of the KP instance, sorted by strictly increasing weight and strictly increasing profit.

Step 2: computation of an optimal solution

To compute an optimal solution, i.e., the binary vector $(x_1,x_2,\dots,x_n)$, it is necessary to store some additional information. The list $L_n$ alone gives the optimal value, but it does not say which items produce the state that attains it.
For each item $j$ and each position $h \in \{1,2,\dots,|L_j|\}$, in addition to the state $L_j[h]$, we store two values:
- ${\sigma}_j[h]$, which is equal to $1$ if item $j$ is selected in the state $L_j[h]$, and is equal to $0$ otherwise;
- ${\rho}_j[h]$, which is the position in $L_{j-1}$ of the state from which $L_j[h]$ is obtained.
A state taken from $L_{j-1}$ gives ${\sigma}_j[h]=0$, while a state taken from $M_j$ gives ${\sigma}_j[h]=1$. In both cases ${\rho}_j[h]$ is the position of the state of $L_{j-1}$ that generated it.
The DP algorithm must also keep all the lists $L_0,L_1,\dots,L_n$, and not only the last one, because the reconstruction goes backwards through them.

Example 17.11: Computation of the additional information

We consider the KP instance of Example 17.1. For each item $j$ and each position $h$, the table shows the state $L_j[h]$ and the stored values ${\sigma}_j[h]$ and ${\rho}_j[h]$.

\[ \begin{array}{c|c|c|c|c} \hline {j} & {h} & {L_j[h]} & {\sigma_j[h]} & {\rho_j[h]} \\ \hline {1} & {1} & {(0,0)} & {0} & {1} \\ {1} & {2} & {(2,6)} & {1} & {1} \\ \hline {2} & {1} & {(0,0)} & {0} & {1} \\ {2} & {2} & {(2,6)} & {0} & {2} \\ {2} & {3} & {(3,7)} & {1} & {1} \\ {2} & {4} & {(5,13)} & {1} & {2} \\ \hline {3} & {1} & {(0,0)} & {0} & {1} \\ {3} & {2} & {(2,6)} & {0} & {2} \\ {3} & {3} & {(3,8)} & {1} & {1} \\ {3} & {4} & {(5,14)} & {1} & {2} \\ \hline \end{array} \]

For instance, the state $L_3[4]=(5,14)$ has ${\sigma}_3[4]=1$ and ${\rho}_3[4]=2$: it is obtained by selecting item $3$ from the state $L_2[2]=(2,6)$, since $2+w_3=2+3=5$ and $6+p_3=6+8=14$.
Once the lists and the stored values have been computed, an optimal solution is reconstructed by scanning the items from $j=n$ down to $j=1$, starting from the last position $h=|L_n|$, which holds the state of largest profit:

\[ \begin{array}{ll} x_j \leftarrow {\sigma}_j[h],\quad h \leftarrow {\rho}_j[h] & \textrm{for $j=n,n-1,\dots,1$.} \end{array} \]

This yields the vector $(x_1,x_2,\dots,x_n)$, where $x_j$ is equal to $1$ if item $j$ is selected in an optimal solution, and $0$ otherwise.

Algorithm: DP_Lists_Reconstruct

Input: The number $n$ of items, the lists $L_0,L_1,\dots,L_n$, and the stored values ${\sigma}$ and ${\rho}$

Output: An optimal solution of the KP instance

1Function DP_Lists_Reconstruct($n,L,\sigma,\rho$)

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

3for $j := 1$ to $n$ do

4$x[j] \leftarrow 0$

5end

6$h := |L_n|$

7for $j := n$ downto $1$ do

8$x[j] \leftarrow {\sigma}_j[h]$

9$h \leftarrow {\rho}_j[h]$

10end

11return $x$

Example 17.12: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 17.1, the last list is

\[ L_3=\big\{(0,0),(2,6),(3,8),(5,14)\big\} \]

and the optimal value is the profit of its last state, that is $14$.

We can reconstruct an optimal solution by starting from $j=3$ and $h=|L_3|=4$ as follows:

Iteration	$j$	$h$	$L_j[h]$	${\sigma}_j[h]$	${\rho}_j[h]$	$x[1]$	$x[3]$	Action
$-$	$-$	$-$	$-$	$-$	$-$	0	0	$h=4$
$1$	$3$	$4$	$(5,14)$	$1$	$2$	0	1	$h\leftarrow 2$
$2$	$2$	$2$	$(2,6)$	$0$	$2$	0	1	$h\leftarrow 2$
$3$	$1$	$2$	$(2,6)$	$1$	$1$	1	1	$h\leftarrow 1$

Thus, the vector

\[ (1,0,1) \]

is an optimal solution. The corresponding optimal value is $6+8=14$.

17.2.3 Number of steps¶

Let $S(n,c)$ denote the number of steps executed by DP_Lists in the worst case, where $n$ is the number of items and $c$ is the knapsack capacity.
The states of a list have strictly increasing weights, and every weight belongs to $\{0,1,\dots,c\}$: therefore $|L_j|\le c+1$ for all $j \in \{0,1,\dots,n\}$, and $|M_j|\le|L_{j-1}|$.
For each item, DP_Lists scans $L_{j-1}$ once to build $M_j$ and then calls Merge, which scans $|L_{j-1}|+|M_j|\le 2(c+1)$ states and performs a constant number of operations for each of them.
Therefore the number of steps executed for each item is $\Theta(c)$ in the worst case, and

\[ S(n,c)=\Theta(nc). \]
The three implementations have the same order of growth, but they do not store the same amount of information. The matrix ${v}$ always has $(n+1)(c+1)$ cells, while the lists contain only the states that are actually reachable: a list reaches the bound $c+1$ only when every capacity value is the total weight of a subset of the items.
On the KP instance of Example 17.1 the lists contain $1$, $2$, $4$, and $4$ states, against the $24$ cells of the matrix ${v}$.
The list $L_j$ also satisfies $|L_j|\le 2^j$, since the items $\{1,2,\dots,j\}$ have $2^j$ subsets. Therefore

\[ |L_j|\le \min\big\{2^j,\,c+1\big\}, \]

and the number of states stays small while $j$ is small, whatever the knapsack capacity.

Next: 17.3 A second DP algorithm

\(j\)	state	from	Action
\(1\)	\((0,0)\)	\(L_{0}\)	\(0>\pi=-1\): append
\(1\)	\((2,6)\)	\(M_1\)	\(6>\pi=0\): append
\(2\)	\((0,0)\)	\(L_{1}\)	\(0>\pi=-1\): append
\(2\)	\((2,6)\)	\(L_{1}\)	\(6>\pi=0\): append
\(2\)	\((3,7)\)	\(M_2\)	\(7>\pi=6\): append
\(2\)	\((5,13)\)	\(M_2\)	\(13>\pi=7\): append
\(3\)	\((0,0)\)	\(L_{2}\)	\(0>\pi=-1\): append
\(3\)	\((2,6)\)	\(L_{2}\)	\(6>\pi=0\): append
\(3\)	\((3,8)\)	\(M_3\)	\(8>\pi=6\): append
\(3\)	\((3,7)\)	\(L_{2}\)	\(7\le\pi=8\): discard (dominated)
\(3\)	\((5,14)\)	\(M_3\)	\(14>\pi=8\): append
\(3\)	\((5,13)\)	\(L_{2}\)	\(13\le\pi=14\): discard (dominated)

Iteration	\(j\)	\(h\)	\(L_j[h]\)	\({\sigma}_j[h]\)	\({\rho}_j[h]\)	\(x[1]\)	\(x[3]\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	\(-\)	\(-\)	0	0	\(h=4\)
\(1\)	\(3\)	\(4\)	\((5,14)\)	\(1\)	\(2\)	0	1	\(h\leftarrow 2\)
\(2\)	\(2\)	\(2\)	\((2,6)\)	\(0\)	\(2\)	0	1	\(h\leftarrow 2\)
\(3\)	\(1\)	\(2\)	\((2,6)\)	\(1\)	\(1\)	1	1	\(h\leftarrow 1\)