DP for the multiple knapsack problem¶

Part 3 · Dynamic programming · Chapter 24 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Multiple knapsack (MKP)

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 knapsack problem, with $m$ knapsacks of capacities $c_1,\dots,c_m$.
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(j,k_1,\dots,k_m)$ over the items and the residual capacities of the $m$ knapsacks;
run the DP algorithm by hand on an instance with $m=2$ knapsacks, one matrix for each item;
reconstruct an optimal solution, with the knapsack of every selected item, from the tables $s$;
count the $\Theta(m\,n\prod_{i=1}^{m}(c_i+1))$ steps and explain why the number of states grows exponentially with $m$.

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

24.1 A DP algorithm¶

We write $i\in\mathscr{K}=\{1,2,\dots,m\}$ for a generic knapsack, because in the DP chapters the letter $k$ denotes a capacity. Knapsack $i$ has capacity $c_i$.
A solution assigns each item $j$ to one knapsack or leaves it out: it is described by the vector $(a_1,a_2,\dots,a_n)$, where $a_j=i$ if item $j$ is inserted into knapsack $i$, and $a_j=0$ if item $j$ is not selected.
The vector $\vet{e}_i$ is the $i$-th unit vector of length $m$: $\vet{k}-w_j\vet{e}_i$ is the vector $\vet{k}$ with the component $k_i$ decreased by $w_j$.

Example 24.1: MKP instance

We consider $m=2$ knapsacks with capacities $c_1=5$ and $c_2=4$, and a set $\mathscr{I}=\{1,2,3,4\}$ of $4$ items ($n=4$), with the following profits and weights:

\[ \begin{array}{l|rrrr} \hline & {j=1} & {j=2} & {j=3} & {j=4} \\ \hline {p_j} & 3 & 9 & 7 & 5 \\ {w_j} & 3 & 4 & 4 & 2 \\ \hline \end{array} \]

We refer to this MKP instance as Example 24.1.

Step 1: computation of the optimal value
For any $j \in \{0,1,\dots,n\}$ and any vector $\vet{k}=(k_1,k_2,\dots,k_m)$ with $k_i \in \{0,1,\dots,c_i\}$ for every $i\in\mathscr{K}$, let $v(j,\vet{k})=v(j,k_1,\dots,k_m)$ be the optimal value of the MKP subinstance given by:
1. $m$ knapsacks, knapsack $i$ with capacity $k_i$,
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 recursive formula to compute $v(j,\vet{k})$ reads as follows:

\[\begin{equation*} \label{eq:mkp} v(j,\vet{k})= \left\{ \begin{array}{ll} 0 & \textrm{if $j=0$,}\\[2ex] v(j-1,\vet{k}) & \begin{array}[t]{@{}l@{}}\textrm{if $j\ge 1$ and}\\ \textrm{$w_j>k_i$ for all $i$,}\end{array}\\[4ex] \begin{array}[t]{@{}l@{}}\displaystyle \max \big\{ v(j-1,\vet{k}),\\ \quad p_j+\displaystyle\max_{i:\,w_j\le k_i} v(j-1,\vet{k}-w_j\vet{e}_i) \big\}\end{array} & \begin{array}[t]{@{}l@{}}\textrm{if $j\ge 1$ and}\\ \textrm{$w_j\le k_i$ for some $i$.}\end{array} \end{array} \right. \tag{24.1} \end{equation*}\]
- The components of $\vet{k}$ are the residual capacities of the knapsacks: in the top-down view, the decisions on the items $j+1,\dots,n$ have already used $c_i-k_i$ units of knapsack $i$.
- With $m=1$ the formula $\eqref{eq:mkp}$ is the recurrence of the KP.
- The base cases are $v(0,\vet{k})=0$ for every vector $\vet{k}$, since no item is available.
- The formula generates at most $m+1$ independent subproblems: item $j$ is left out, or it is inserted into one of the knapsacks $i$ with $w_j\le k_i$, and then only the capacity of knapsack $i$ decreases.
  
  $\rightsquigarrow$ Optimal Substructure verified!
- Different assignments of the items $j+1,\dots,n$ can leave the same residual capacities, and therefore the same value $v(j,\vet{k})$ may be needed several times.
  
  $\rightsquigarrow$ Overlapping Subproblems verified!
- The value $v(j,\vet{k})$ depends only on values of row $j-1$. Therefore, the bottom-up approach computes the rows $j=0,1,\dots,n$ in this order, and in each row all the vectors $\vet{k}$ in any order. With $m=2$ the row $j$ is a matrix, with one row for each $k_1$ and one column for each $k_2$.

Step 2: computation of an optimal solution

For each item $j$ and vector $\vet{k}$ we store $s[j][\vet{k}]=i$ if item $j$ is inserted into knapsack $i$ in the optimal solution found for $(j,\vet{k})$, and $s[j][\vet{k}]=0$ if item $j$ is left out.
The set of all the vectors $\vet{k}$ is $\mathscr{C}=\{0,1,\dots,c_1\}\times\{0,1,\dots,c_2\}\times\dots\times\{0,1,\dots,c_m\}$.

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

Algorithm: MKP_DP

Input: An MKP instance given by $n$, $m$, arrays $p[1..n]$, $w[1..n]$, and the capacity vector $\vet{c}$

Output: The optimal value of the MKP instance and the tables $s[j][\vet{k}]$

1Function MKP_DP($n,m,p,w,\vet{c}$)

2$v := \textnormal{new array}[0..n][0..c_1]\cdots[0..c_m]$; $s := \textnormal{new array}[0..n][0..c_1]\cdots[0..c_m]$

3for each $\vet{k} \in \mathscr{C}$ do

4$v[0][\vet{k}] \leftarrow 0$; $s[0][\vet{k}] \leftarrow 0$

5end

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

7for each $\vet{k} \in \mathscr{C}$ do

8$v[j][\vet{k}] \leftarrow v[j-1][\vet{k}]$; $s[j][\vet{k}] \leftarrow 0$

9for $i := 1$ to $m$ do

10if $w[j]\le k_i$ and $p[j]+v[j-1][\vet{k}-w[j]\,\vet{e}_i] > v[j][\vet{k}]$ then

11$v[j][\vet{k}] \leftarrow p[j]+v[j-1][\vet{k}-w[j]\,\vet{e}_i]$; $s[j][\vet{k}] \leftarrow i$

12end

13end

14end

15end

16return $v[n][\vet{c}], s$

For each vector $\vet{k}$, the DP algorithm first leaves item $j$ out, and then tries to insert it into each knapsack $i=1,2,\dots,m$ in which it fits.
In case of ties the first option met is kept: leaving item $j$ out, then the knapsack of smallest index, because the value is updated only when it is strictly larger.

Example 24.2: Execution of the DP algorithm

We consider the MKP instance of Example 24.1, with capacities $c_1=5$ and $c_2=4$. The row $j=0$ is $v[0][\vet{k}]=0$ for every $\vet{k}$. For each item $j$ we compute the matrix $v[j][k_1][k_2]$, with one row for each $k_1\in\{0,1,\dots,5\}$ and one column for each $k_2\in\{0,1,\dots,4\}$.

These are the computations of the cell $\vet{k}=\vet{c}=(5,4)$ for each item, and of the cells used by the reconstruction:

$v[1][(5,4)]=\max\{v[0][(5,4)],\,p_1+v[0][(2,4)],\,p_1+v[0][(5,1)]\}=\max\{0,\,3+0,\,3+0\}=3$
$v[1][(3,0)]=\max\{v[0][(3,0)],\,p_1+v[0][(0,0)]\}=\max\{0,\,3+0\}=3$
$v[2][(5,4)]=\max\{v[1][(5,4)],\,p_2+v[1][(1,4)],\,p_2+v[1][(5,0)]\}=\max\{3,\,9+3,\,9+3\}=12$
$v[2][(3,4)]=\max\{v[1][(3,4)],\,p_2+v[1][(3,0)]\}=\max\{3,\,9+3\}=12$
$v[3][(5,4)]=\max\{v[2][(5,4)],\,p_3+v[2][(1,4)],\,p_3+v[2][(5,0)]\}=\max\{12,\,7+9,\,7+9\}=16$
$v[3][(3,4)]=\max\{v[2][(3,4)],\,p_3+v[2][(3,0)]\}=\max\{12,\,7+3\}=12$
$v[4][(5,4)]=\max\{v[3][(5,4)],\,p_4+v[3][(3,4)],\,p_4+v[3][(5,2)]\}=\max\{16,\,5+12,\,5+9\}=17$

Item $j=1$, with $p_1=3$ and $w_1=3$:

\[ \begin{array}{l|rrrrr} \hline {v[1][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {3} & {3} \\ {k_1=1} & {0} & {0} & {0} & {3} & {3} \\ {k_1=2} & {0} & {0} & {0} & {3} & {3} \\ {k_1=3} & {3} & {3} & {3} & {3} & {3} \\ {k_1=4} & {3} & {3} & {3} & {3} & {3} \\ {k_1=5} & {3} & {3} & {3} & {3} & {3} \\ \hline \end{array} \]

Item $j=2$, with $p_2=9$ and $w_2=4$:

\[ \begin{array}{l|rrrrr} \hline {v[2][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {3} & {9} \\ {k_1=1} & {0} & {0} & {0} & {3} & {9} \\ {k_1=2} & {0} & {0} & {0} & {3} & {9} \\ {k_1=3} & {3} & {3} & {3} & {3} & {12} \\ {k_1=4} & {9} & {9} & {9} & {12} & {12} \\ {k_1=5} & {9} & {9} & {9} & {12} & {12} \\ \hline \end{array} \]

Item $j=3$, with $p_3=7$ and $w_3=4$:

\[ \begin{array}{l|rrrrr} \hline {v[3][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {3} & {9} \\ {k_1=1} & {0} & {0} & {0} & {3} & {9} \\ {k_1=2} & {0} & {0} & {0} & {3} & {9} \\ {k_1=3} & {3} & {3} & {3} & {3} & {12} \\ {k_1=4} & {9} & {9} & {9} & {12} & {16} \\ {k_1=5} & {9} & {9} & {9} & {12} & {16} \\ \hline \end{array} \]

Item $j=4$, with $p_4=5$ and $w_4=2$:

\[ \begin{array}{l|rrrrr} \hline {v[4][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {5} & {5} & {9} \\ {k_1=1} & {0} & {0} & {5} & {5} & {9} \\ {k_1=2} & {5} & {5} & {5} & {8} & {14} \\ {k_1=3} & {5} & {5} & {8} & {8} & {14} \\ {k_1=4} & {9} & {9} & {14} & {14} & {16} \\ {k_1=5} & {9} & {9} & {14} & {14} & {17} \\ \hline \end{array} \]

Example 24.3: The tables $s$

For the instance of Example 24.1, these are the matrices $s[j][k_1][k_2]$ computed by the DP algorithm: $0$ means that item $j$ is left out, $1$ and $2$ the knapsack into which it is inserted.

Item $j=1$, with $p_1=3$ and $w_1=3$:

\[ \begin{array}{l|rrrrr} \hline {s[1][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {2} & {2} \\ {k_1=1} & {0} & {0} & {0} & {2} & {2} \\ {k_1=2} & {0} & {0} & {0} & {2} & {2} \\ {k_1=3} & {1} & {1} & {1} & {1} & {1} \\ {k_1=4} & {1} & {1} & {1} & {1} & {1} \\ {k_1=5} & {1} & {1} & {1} & {1} & {1} \\ \hline \end{array} \]

Item $j=2$, with $p_2=9$ and $w_2=4$:

\[ \begin{array}{l|rrrrr} \hline {s[2][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {2} \\ {k_1=1} & {0} & {0} & {0} & {0} & {2} \\ {k_1=2} & {0} & {0} & {0} & {0} & {2} \\ {k_1=3} & {0} & {0} & {0} & {0} & {2} \\ {k_1=4} & {1} & {1} & {1} & {1} & {1} \\ {k_1=5} & {1} & {1} & {1} & {1} & {1} \\ \hline \end{array} \]

Item $j=3$, with $p_3=7$ and $w_3=4$:

\[ \begin{array}{l|rrrrr} \hline {s[3][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {0} & {0} & {0} \\ {k_1=1} & {0} & {0} & {0} & {0} & {0} \\ {k_1=2} & {0} & {0} & {0} & {0} & {0} \\ {k_1=3} & {0} & {0} & {0} & {0} & {0} \\ {k_1=4} & {0} & {0} & {0} & {0} & {1} \\ {k_1=5} & {0} & {0} & {0} & {0} & {1} \\ \hline \end{array} \]

Item $j=4$, with $p_4=5$ and $w_4=2$:

\[ \begin{array}{l|rrrrr} \hline {s[4][k_1][k_2]} & {k_2=0} & {k_2=1} & {k_2=2} & {k_2=3} & {k_2=4} \\ \hline {k_1=0} & {0} & {0} & {2} & {2} & {0} \\ {k_1=1} & {0} & {0} & {2} & {2} & {0} \\ {k_1=2} & {1} & {1} & {1} & {1} & {1} \\ {k_1=3} & {1} & {1} & {2} & {1} & {1} \\ {k_1=4} & {0} & {0} & {2} & {2} & {0} \\ {k_1=5} & {0} & {0} & {2} & {2} & {1} \\ \hline \end{array} \]

Once the tables $s$ have been computed, an optimal solution is reconstructed by scanning the items from $j=n$ down to $j=1$, starting from $\vet{k}=\vet{c}$ and $a_j=0$ for every item $j$:

\[ a_j \leftarrow s[j][\vet{k}], \qquad \textrm{and, if } a_j=i\ge 1,\quad \vet{k} \leftarrow \vet{k} - w_j\vet{e}_i. \]

Algorithm: MKP_Reconstruct

Input: The number $n$ of items, the capacity vector $\vet{c}$, the array $w[1..n]$, and the tables $s$

Output: An optimal solution of the MKP instance, as the vector of the knapsacks

1Function MKP_Reconstruct($n,\vet{c},w,s$)

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

3$\vet{k} := \vet{c}$

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

5$a[j] \leftarrow s[j][\vet{k}]$

6if $a[j]\ge 1$ then

7$\vet{k} \leftarrow \vet{k}-w[j]\,\vet{e}_{a[j]}$

8end

9end

10return $a$

Example 24.4: Computing an optimal solution

After the execution of the DP algorithm on the instance of Example 24.1, we start from $j=4$ and $\vet{k}=(5,4)$:

Iteration	$j$	$\vet{k}$	$s[j][\vet{k}]$	$a[1]$	$a[2]$	$a[4]$	Action
$-$	$-$	$-$	$-$	0	0	0	$\vet{k}=(5,4)$
$1$	$4$	$(5,4)$	$1$	0	0	1	$a[4]\leftarrow 1$, $\vet{k}\leftarrow (3,4)$
$2$	$3$	$(3,4)$	$0$	0	0	1	$a[3]\leftarrow 0$, $\vet{k}=(3,4)$
$3$	$2$	$(3,4)$	$2$	0	2	1	$a[2]\leftarrow 2$, $\vet{k}\leftarrow (3,0)$
$4$	$1$	$(3,0)$	$1$	1	2	1	$a[1]\leftarrow 1$, $\vet{k}\leftarrow (0,0)$

The vector $a=(1,2,0,1)$ is an optimal solution of the MKP instance of Example 24.1: knapsack $1$ contains the items $\{1,4\}$, of total weight $3+2=5\le c_1$, and knapsack $2$ contains the items $\{2\}$, of total weight $4\le c_2$. The optimal value is $v(4,5,4)=17$.

Filling the knapsacks one after the other is not enough: the best filling of knapsack $1$ alone is $\{2\}$, of profit $9$, and the best filling of knapsack $2$ with the remaining items is $\{3\}$, of profit $7$, for a total of $16<17$.

24.1.1 Number of steps¶

Let $N=|\mathscr{C}|=\prod_{i=1}^{m}(c_i+1)$ be the number of vectors $\vet{k}$, and let $S(n,m,\vet{c})$ denote the number of steps executed by MKP_DP in the worst case. Inserting item $j$ into knapsack $i$ changes only the component $k_i$, so lines 10 and 11 count one step each:
- Lines 2 and 16 are executed $1$ time each.
- Lines 3 and 4 are executed $N$ times each.
- Line 6 is executed $n$ times.
- Lines 7 and 8 are executed $nN$ times each.
- Lines 9, 10 and 11 are executed at most $m\,nN$ times each.
Therefore, the total number of steps in the worst case is

\[ S(n,m,\vet{c})=3m\,nN+2nN+2N+n+2, \]

and, since $3m\,nN\le S(n,m,\vet{c})\le 10m\,nN$,

\[ S(n,m,\vet{c})=\Theta\Big(m\,n\prod_{i=1}^{m}(c_i+1)\Big). \]

The DP algorithm for the MKP executes $\Theta(m\,n\prod_{i=1}^{m}(c_i+1))$ steps in the worst case. For a fixed number $m$ of knapsacks this is $\Theta(n\prod_{i=1}^{m}c_i)$, a pseudo-polynomial number of steps.
The reconstruction executes $\Theta(n)$ steps.

24.1.2 The growth with the number of knapsacks¶

Each new knapsack multiplies the number of states by $c_i+1$. If all the capacities are equal to $c$, the table has $(n+1)(c+1)^m$ cells: the number of states grows exponentially with $m$, while the size of the input grows only by one number, the capacity $c_i$.
With $n=50$ items and capacities $c_i=100$, the table has $51\cdot 101=5151$ cells with $m=1$, $51\cdot 101^2=520\,251$ with $m=2$, and $51\cdot 101^5\approx 5.4\cdot 10^{11}$ with $m=5$.
Knapsacks with the same capacity give symmetric states: if $c_1=c_2$, the vectors $(k_1,k_2,\dots)$ and $(k_2,k_1,\dots)$ have the same optimal value, and the DP algorithm computes both.

24.2 Typical mistakes¶

Warning

Decreasing all the capacities. Item $j$ goes into one knapsack only: $\vet{k}-w_j\vet{e}_i$ decreases the component $k_i$, not all of them as in the multidimensional knapsack problem.
Using one capacity $c_1+\dots+c_m$. The KP with the total capacity gives only an upper bound: its solution may not be divisible among the knapsacks.
Filling the knapsacks one after the other. An optimal filling of knapsack $1$, followed by an optimal filling of knapsack $2$ with the remaining items, can be worse than the optimum.
Forgetting the option «item left out». The term $v(j-1,\vet{k})$ is always a candidate, also when item $j$ fits into some knapsack.

24.3 In summary¶

In summary

The state of the DP algorithm is the item $j$ and the vector $\vet{k}$ of the residual capacities of the $m$ knapsacks.
Item $j$ is left out or inserted into one knapsack $i$ in which it fits: $m+1$ options, and only $k_i$ decreases.
The DP algorithm executes $\Theta(m\,n\prod_{i=1}^{m}(c_i+1))$ steps: the number of states grows exponentially with $m$.
The tables $s$ store the knapsack of each item, and an optimal solution is read backwards from $(n,\vet{c})$.

Dashboard of the MKP example. Example 24.1 ($\vet{c}=(5,4)$, four items):

Method	Lower bound	Upper bound	Origin
DP algorithm	$17$	$17$	optimal value, solution $a=(1,2,0,1)$

Exercises on this chapter: Multiple knapsack (MKP)

Iteration	\(j\)	\(\vet{k}\)	\(s[j][\vet{k}]\)	\(a[1]\)	\(a[2]\)	\(a[4]\)	Action
\(-\)	\(-\)	\(-\)	\(-\)	0	0	0	\(\vet{k}=(5,4)\)
\(1\)	\(4\)	\((5,4)\)	\(1\)	0	0	1	\(a[4]\leftarrow 1\), \(\vet{k}\leftarrow (3,4)\)
\(2\)	\(3\)	\((3,4)\)	\(0\)	0	0	1	\(a[3]\leftarrow 0\), \(\vet{k}=(3,4)\)
\(3\)	\(2\)	\((3,4)\)	\(2\)	0	2	1	\(a[2]\leftarrow 2\), \(\vet{k}\leftarrow (3,0)\)
\(4\)	\(1\)	\((3,0)\)	\(1\)	1	2	1	\(a[1]\leftarrow 1\), \(\vet{k}\leftarrow (0,0)\)