DP for the subset sum problem

Part 3 · Dynamic programming · Chapter 20 · Lecture notes, volume 3 (PDF) · Slides · Exercises: Subset sum (SSP) · App: DP tables for the knapsack problems

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 subset sum problem and its solution as a 0/1 knapsack problem with \(p_j=w_j\).

• 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 \(r(j,k)\in\{\textit{true},\textit{false}\}\) of the reachable sums, with its base cases;

• run the DP algorithm by hand and read the answer of the SSP instance in \(r(n,c)\);

• fill the matrix \(s\) and reconstruct a subset of total weight \(c\) when the answer is yes;

• relate \(r(j,k)\) to the DP algorithm of the KP with \(p_j=w_j\), and count the \(\Theta(nc)\) steps.

The problem of this chapter is the subset sum problem (SSP): its definition and its assumptions are on its page.

20.1 A DP algorithm

Example 20.1: SSP instance

We consider a target value \(c=10\) and a set \(\mathscr{I}=\{1,2,3,4\}\) of \(4\) items (\(n=4\)), with the following weights:

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

We refer to this SSP instance as Example 20.1.

• A subset \(S\subseteq\mathscr{I}\) is described by the binary vector \((x_1,x_2,\dots,x_n)\), where \(x_j=1\) if item \(j\) belongs to \(S\) and \(x_j=0\) otherwise.

• The answer to the SSP instance is yes if some vector satisfies \(\sum_{j=1}^{n} w_j x_j = c\), and no otherwise.

• Step 1: computation of the answer

  For any \(j \in \{0,1,\dots,n\}\) and \(k \in \{0,1,\dots,c\}\), let \(r(j,k)\in\{\textit{true},\textit{false}\}\) be the answer of the SSP subinstance given by:

  1. a target value \(k\),

  2. a set \(\{1,2,\dots,j\}\) of available items,

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

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

  \[\begin{equation*} \label{eq:ssp} r(j,k)= \left\{ \begin{array}{ll} \textit{true} & \textrm{if $k=0$,}\\[2ex] \textit{false} & \textrm{if $j=0$ and $k\ge 1$,}\\[2ex] r(j-1,k) & \textrm{if $j,k\ge 1$ and $w_j>k$,}\\[2ex] r(j-1,k) \,\lor\, r(j-1,k-w_j) & \textrm{if $j,k\ge 1$ and $w_j\le k$.} \end{array} \right. \tag{20.1} \end{equation*}\]

  • The symbol \(\lor\) is the logical or: \(r(j,k)\) is true if at least one of the two values is true.

  • The base cases are \(r(j,0)=\textit{true}\), since the empty subset has total weight \(0\), and \(r(0,k)=\textit{false}\) for \(k\ge 1\), since no item is available.

  • A subset of \(\{1,2,\dots,j\}\) with total weight \(k\) either does not contain item \(j\), and then it is a subset of \(\{1,2,\dots,j-1\}\) with total weight \(k\), or it contains item \(j\), and then the other items form a subset of \(\{1,2,\dots,j-1\}\) with total weight \(k-w_j\).

  • Hence, the formula \(\eqref{eq:ssp}\) generates at most \(2\) independent subproblems, and a subset for \((j,k)\) is built from a subset of one of them by adding item \(j\) or not.

    \(\rightsquigarrow\) Optimal Substructure verified!

  • Different decisions on the items can lead to the same pair \((j,k)\), and therefore the same value \(r(j,k)\) may be needed several times during the recursive evaluation of formula \(\eqref{eq:ssp}\).

    \(\rightsquigarrow\) Overlapping Subproblems verified!

  • The value \(r(j,k)\) depends only on values \(r(j-1,k')\) with \(k'\le k\). Therefore, the bottom-up approach computes the rows \(j=0,1,\dots,n\) in this order, each one for increasing \(k\), and stores every value in a lookup table.

  • The SSP can also be solved by the DP algorithm of the KP with \(p_j=w_j\) for every item \(j\). Its value \(v(j,k)\) is the largest total weight, not larger than \(k\), of a subset of \(\{1,2,\dots,j\}\), and

    \[ r(j,k)=\textit{true} \iff v(j,k)=k. \]

  • The recurrence \(\eqref{eq:ssp}\) stores only one bit per cell, and its logical operations replace the sums and the comparisons of the KP recurrence.

• Step 2: computation of a subset

  • When the answer is yes, a subset of total weight \(c\) is reconstructed from the matrix \(s\): \(s[j][k]=1\) if item \(j\) is used to reach the value true of \(r[j][k]\), and \(s[j][k]=0\) otherwise.

  • The DP algorithm prefers not to use item \(j\): \(s[j][k]=1\) only if \(r[j-1][k]\) is false and \(r[j-1][k-w_j]\) is true.

  This is the pseudo-code of the DP algorithm using the bottom-up approach, which stores the matrix \(s\) together with the matrix \(r\):

  Algorithm: SSP_DP

  Input: An SSP instance given by \(n\), the array \(w[1..n]\), and the target value \(c\)

  Output: The answer \(r[n][c]\) of the SSP instance and the matrix \(s[0..n][0..c]\)

  1Function SSP_DP(\(n,w,c\))

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

  3\(r[0][0] \leftarrow \textit{true}\); \(s[0][0] \leftarrow 0\)

  4for \(k := 1\) to \(c\) do

  5\(r[0][k] \leftarrow \textit{false}\); \(s[0][k] \leftarrow 0\)

  6end

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

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

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

  10if \(r[j][k]=\textit{false}\) and \(w[j]\le k\) and \(r[j-1][k-w[j]]=\textit{true}\) then

  11\(r[j][k] \leftarrow \textit{true}\); \(s[j][k] \leftarrow 1\)

  12end

  13end

  14end

  15return \(r[n][c], s\)

  • The matrix \(r[0..n][0..c]\) is the lookup table of the answers, and the matrix \(s[0..n][0..c]\) stores the decisions.

  • Lines 3–5 fill the row \(j=0\): only the target value \(0\) is reachable without items.

  • For each pair \((j,k)\), the DP algorithm first copies the answer without item \(j\), and then uses item \(j\) only if this answer is false and item \(j\) makes the value \(k\) reachable.

  • Finally, the answer of the SSP instance is returned as \(r[n][c]\), together with the matrix \(s\).

  Example 20.2: Execution of the DP algorithm

  We consider the SSP instance of Example 20.1, with target value \(c=10\) and weights \(w=(3,5,4,7)\).

  For each step of the DP algorithm with \(j\ge 1\), the table shows the values of \(j\) and \(k\), the cells \(r[j][k]\) and \(s[j][k]\), and the operation performed; \(\mathrm{T}\) stands for true and \(\mathrm{F}\) for false. The row \(j=0\) is \(r[0][0]=\mathrm{T}\) and \(r[0][k]=\mathrm{F}\) for \(k\ge 1\), with \(s[0][k]=0\).

  \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
  \(1\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_1=3>0\): \(r[0][0]=\mathrm{T}\)
  \(1\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>1\): \(r[0][1]=\mathrm{F}\)
  \(1\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_1=3>2\): \(r[0][2]=\mathrm{F}\)
  \(1\)	\(3\)	\(\mathrm{T}\)	\(1\)	\(r[0][3]\lor r[0][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(1\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(r[0][4]\lor r[0][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(5\)	\(\mathrm{F}\)	\(0\)	\(r[0][5]\lor r[0][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[0][6]\lor r[0][3]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[0][7]\lor r[0][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(8\)	\(\mathrm{F}\)	\(0\)	\(r[0][8]\lor r[0][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[0][9]\lor r[0][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(1\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[0][10]\lor r[0][7]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(2\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_2=5>0\): \(r[1][0]=\mathrm{T}\)
  \(2\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>1\): \(r[1][1]=\mathrm{F}\)
  \(2\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>2\): \(r[1][2]=\mathrm{F}\)
  \(2\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_2=5>3\): \(r[1][3]=\mathrm{T}\)
  \(2\)	\(4\)	\(\mathrm{F}\)	\(0\)	\(w_2=5>4\): \(r[1][4]=\mathrm{F}\)
  \(2\)	\(5\)	\(\mathrm{T}\)	\(1\)	\(r[1][5]\lor r[1][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(2\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[1][6]\lor r[1][1]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(2\)	\(7\)	\(\mathrm{F}\)	\(0\)	\(r[1][7]\lor r[1][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(2\)	\(8\)	\(\mathrm{T}\)	\(1\)	\(r[1][8]\lor r[1][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(2\)	\(9\)	\(\mathrm{F}\)	\(0\)	\(r[1][9]\lor r[1][4]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(2\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[1][10]\lor r[1][5]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)

  \(j\)	\(k\)	\(r[j][k]\)	\(s[j][k]\)	Action
  \(3\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_3=4>0\): \(r[2][0]=\mathrm{T}\)
  \(3\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_3=4>1\): \(r[2][1]=\mathrm{F}\)
  \(3\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_3=4>2\): \(r[2][2]=\mathrm{F}\)
  \(3\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_3=4>3\): \(r[2][3]=\mathrm{T}\)
  \(3\)	\(4\)	\(\mathrm{T}\)	\(1\)	\(r[2][4]\lor r[2][0]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(3\)	\(5\)	\(\mathrm{T}\)	\(0\)	\(r[2][5]\lor r[2][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
  \(3\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(r[2][6]\lor r[2][2]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(3\)	\(7\)	\(\mathrm{T}\)	\(1\)	\(r[2][7]\lor r[2][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(3\)	\(8\)	\(\mathrm{T}\)	\(0\)	\(r[2][8]\lor r[2][4]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
  \(3\)	\(9\)	\(\mathrm{T}\)	\(1\)	\(r[2][9]\lor r[2][5]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)
  \(3\)	\(10\)	\(\mathrm{F}\)	\(0\)	\(r[2][10]\lor r[2][6]=\mathrm{F}\lor \mathrm{F}=\mathrm{F}\)
  \(4\)	\(0\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>0\): \(r[3][0]=\mathrm{T}\)
  \(4\)	\(1\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>1\): \(r[3][1]=\mathrm{F}\)
  \(4\)	\(2\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>2\): \(r[3][2]=\mathrm{F}\)
  \(4\)	\(3\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>3\): \(r[3][3]=\mathrm{T}\)
  \(4\)	\(4\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>4\): \(r[3][4]=\mathrm{T}\)
  \(4\)	\(5\)	\(\mathrm{T}\)	\(0\)	\(w_4=7>5\): \(r[3][5]=\mathrm{T}\)
  \(4\)	\(6\)	\(\mathrm{F}\)	\(0\)	\(w_4=7>6\): \(r[3][6]=\mathrm{F}\)
  \(4\)	\(7\)	\(\mathrm{T}\)	\(0\)	\(r[3][7]\lor r[3][0]=\mathrm{T}\lor \mathrm{T}=\mathrm{T}\)
  \(4\)	\(8\)	\(\mathrm{T}\)	\(0\)	\(r[3][8]\lor r[3][1]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
  \(4\)	\(9\)	\(\mathrm{T}\)	\(0\)	\(r[3][9]\lor r[3][2]=\mathrm{T}\lor \mathrm{F}=\mathrm{T}\)
  \(4\)	\(10\)	\(\mathrm{T}\)	\(1\)	\(r[3][10]\lor r[3][3]=\mathrm{F}\lor \mathrm{T}=\mathrm{T}\)

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

  \[ \begin{array}{l|rrrrrrrrrrr} \hline {r[j][k]} & {k=0} & {k=1} & {k=2} & {k=3} & {k=4} & {k=5} & {k=6} & {k=7} & {k=8} & {k=9} & {k=10} \\ \hline {j=0} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=1} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=2} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} \\ {j=3} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} \\ {j=4} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{F}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} & {\mathrm{T}} \\ \hline \end{array} \]

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

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

  Since \(r[4][10]=\mathrm{T}\), the answer to the SSP instance is yes. For example, \(s[4][10]=1\) since \(r[3][10]=\mathrm{F}\) and \(r[3][3]=\mathrm{T}\): item \(4\) is needed to reach the target value \(10\).

  • Once the matrix \(s\) has been computed and \(r[n][c]\) is true, a subset of total weight \(c\) is reconstructed by scanning the items from \(j=n\) down to \(j=1\), starting from \(k=c\) and \(x_j=0\) for every item \(j\):

    \[ x_j \leftarrow s[j][k], \qquad k \leftarrow k - s[j][k]\,w_j. \]

  • The reconstruction ends with \(k=0\), since every step keeps \(r[j-1][k]\) equal to true.

  Algorithm: SSP_Reconstruct

  Input: The number \(n\) of items, the target value \(c\), the array \(w[1..n]\), and the matrix \(s[0..n][0..c]\), with \(r[n][c]=\textit{true}\)

  Output: A subset of total weight \(c\), as a binary vector

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

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

  3\(k := c\)

  4for \(j := n\) downto \(1\) do

  5\(x[j] \leftarrow s[j][k]\)

  6\(k \leftarrow k-x[j]\,w[j]\)

  7end

  8return \(x\)

  Example 20.3: Computing a subset

  After the execution of the DP algorithm on the instance of Example 20.1, we start from \(j=4\) and \(k=10\):

  Iteration	\(j\)	\(k\)	\(s[j][k]\)	\(x[1]\)	\(x[2]\)	\(x[3]\)	\(x[4]\)	Action
  \(-\)	\(-\)	\(-\)	\(-\)	0	0	0	0	\(k=10\)
  \(1\)	\(4\)	\(10\)	\(1\)	0	0	0	1	\(x[4]\leftarrow 1\), \(k\leftarrow 10-7=3\)
  \(2\)	\(3\)	\(3\)	\(0\)	0	0	0	1	\(x[3]\leftarrow 0\), \(k=3\)
  \(3\)	\(2\)	\(3\)	\(0\)	0	0	0	1	\(x[2]\leftarrow 0\), \(k=3\)
  \(4\)	\(1\)	\(3\)	\(1\)	1	0	0	1	\(x[1]\leftarrow 1\), \(k\leftarrow 3-3=0\)

  The answer to the SSP instance of Example 20.1 is yes: the vector \((1,0,0,1)\) selects the subset \(\{1,4\}\), whose total weight is \(3+7=c\).

20.1.1 Number of steps

• Let \(S(n,c)\) denote the number of steps executed by SSP_DP in the worst case. We count how many times each line of the pseudo-code is executed, assuming that the condition at line 10 is always true:

  • Lines 2 and 3 are executed \(1\) time each.

  • Line 4 is executed \(c\) times, and line 5 \(c\) times.

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

  • Lines 8, 9, 10 and 11 are executed \(n(c+1)\) times each.

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

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

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

  Hence,

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

  since

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

  The DP algorithm for the SSP executes \(S(n,c)=\Theta(nc)\) steps in the worst case, the same number as the DP algorithm of the KP.

• The reconstruction executes \(\Theta(n)\) steps, one for each item.

• The number of steps contains the target value \(c\), a number of the input, and not only the size of the input: it is pseudo-polynomial.

20.2 Typical mistakes

Warning

• Setting \(r(j,0)=\textit{false}\). The target value \(0\) is always reachable with the empty subset; with \(r(j,0)=\textit{false}\) no value would ever become true.

• Setting \(r(0,k)=\textit{true}\) for \(k\ge 1\). Without items, only the target value \(0\) is reachable.

• Reading the answer in the wrong cell. The answer is \(r(n,c)\); a true value in another cell of the last row says that a different target value is reachable.

• Reconstructing when the answer is no. If \(r(n,c)\) is false, no subset has total weight \(c\), and the matrix \(s\) gives nothing to reconstruct.

20.3 In summary

In summary

• The recurrence \(r(j,k)=r(j-1,k)\lor r(j-1,k-w_j)\) tells whether the target value \(k\) is reachable with the items \(1,2,\dots,j\).

• The base cases are \(r(j,0)=\textit{true}\) and \(r(0,k)=\textit{false}\) for \(k\ge 1\); the answer is \(r(n,c)\).

• The matrix \(s\) stores whether item \(j\) is used, and a subset of total weight \(c\) is read backwards from \((n,c)\).

• The DP algorithm executes \(\Theta(nc)\) steps, as the DP algorithm of the KP with \(p_j=w_j\).

Dashboard of the SSP example. Example 20.1 (\(c=10\), four items):

Method	Answer	Origin
DP algorithm	yes	\(r(4,10)=\textit{true}\), subset \(\{1,4\}\)

---

Exercises on this chapter: Subset sum (SSP)

In the interactive lab: DP tables for the knapsack problems.