35 The Subset Sum Problem

Setting

• We are given $n$ items $\{1,2,\cdots ,n\}$
• Each item $i$ has a non-negative internal weight given by $\mathrm{Weight}(i)$
• A number $W$ is given as an upper bound

The

Given a set $\{1,2,\cdots ,n\}$ of $n$ items with weights $\mathrm{Weight}(1),\mathrm{Weight}(2),\cdots ,\mathrm{Weight}(n)$ respectively and a bound $W$, find a set $S$ of items such that ${\sum }_{i\in S}\mathrm{Weight}(i)$ is maximised subject to the constraint ${\sum }_{i\in S}\mathrm{Weight}(i)\le W$.

Attempting to design a DP algorithm

• Let $\mathrm{OPT}(i)$ denote the max weight of choosing items from $\{1,2,\cdots ,i\}$ such that the sum of weights is maximised subject to being at most $W$.
• Final answer would be $\mathrm{OPT}[n]$
• If item $i$ is not chosen in this set, then $\mathrm{OPT}[i]=\mathrm{OPT}[i-1]$
• But if item $i$ is chosen in this set, then $\mathrm{OPT}[i]$ contains $\mathrm{Weight}(i)$ plus optimal way to choose items from $\{1,2,\cdots ,i-1\}$ with weight at most $W-\mathrm{Weight}(i)$
• We are not remembering this in $\mathrm{OPT}[i-1]$
  • $\mathrm{OPT}[i-1]$ only stores max weight of choosing items from $\{1,2,\cdots ,i\}$ subject to weight being at most $W$.
• So one variable is not enough: we need to store a table
• For each $1\le i\le n$ and $1\le X\le W$,
  • let $\mathrm{OPT}[i,X]$ be the max weight of choosing items from $\{1,2,\cdots ,i\}$ subject to weight being at most $X$.

Obtaining the recurrence

Let $\mathrm{OPT}[i,X]$ be the max weight of choosing items from $\{1,2,\cdots ,i\}$ subject to weight being at most $X$

1. If $i$ is not chosen, then we have
   • $\mathrm{OPT}[i,X]=\mathrm{OPT}[i-1,X]$
   • This is enforced if $\mathrm{Weight}(i)>X$
2. If $i$ is chosen, the wen have
   • $\mathrm{OPT}[i,X]=\mathrm{Weight}(i)+\mathrm{OPT}[i-1,X-\mathrm{Weight}(i)]$

Hence, we obtain the following recurrence

$$\mathrm{OPT}[i,X]=\max \{\mathrm{OPT}[i-1,X];\mathrm{Weight}(i)+\mathrm{OPT}[i-1,X-\mathrm{Weight}(i)]\}$$

Algorithm

$$\begin{array}{rl}\text{Algorithm }& \text{Subset-Sum}(n,W)\\ 1:& \text{We maintain an }(n+1)\times (W+1)\text{ table indexed by }0\le i\le n\text{ and }0\le X\le W\\ & \text{where }\mathrm{OPT}[i,X]\text{ stores the max weight of choosing items from }\{1,2,\dots ,i\}\\ & \text{subject to weight being at most }X.\\ 2:& \text{Initialize }\mathrm{OPT}[0,Y]=0\text{ for each }0\le Y\le W\\ 3:& \text{for }i=1,2,\dots ,n\text{ do}\\ 4:& \text{for each }Z=0,1,2,\dots ,W\text{ do}\\ 5:& \mathrm{OPT}[i,Z]=\max \left\{\mathrm{OPT}[i-1,Z],\mathrm{Weight}(i)+\mathrm{OPT}[i-1,Z-\mathrm{Weight}(i)]\right\}\\ 6:& \text{end for}\\ 7:& \text{end for}\\ & \text{return }\mathrm{OPT}[n,W]\end{array}$$

Correctness

• Proof by induction on $i$
• Base case is $i=0$
• Inductive step is essentially argues the correctness of the recurrence from line 5

Running time

• The table has $O(n\cdot W)$ entries
• Filling up a new entry in the table needs to look-up two existing entries from the table, and do one addition & one max operation
  • This needs constant time
• Hence, time required to fill up all entries is $O(n\cdot W)$