## Dynamic Programming – 3 : Subset Sum

Subset Sum

We are given $n$ items $\{I_1, \ldots, I_n \}$, each having non-negative integral weight $w_i$. We are also given a non-negative integral weight bound $W$. Our task is to find a valid subset of items which maximizes the total weight of the items in the subset.

Terminology: A valid subset $T$ is one such that the total weight of items in $T$ is at most $W$.

Solution.

For item $I_n$, we have 2 choices : either to include it in the optimum solution, or to not include it.(Note that if $w_n > W$, then we have just one choice  — exclude $I_n$ from the optimum solution.)

Case 1:

If $I_n$ is included in the optimum solution, the optimum solution would be $w_n$ plus the optimum solution obtained from the set of items $\{I_1, \ldots, I_{n-1}\}$ with the weight bound as $W-w_n$.

Notation: Let OPT (i, w) denote the value of the optimum solution obtained on the set $\{I_1, \ldots, I_i\}$ with weight bound $w$.The original task, then, is to compute $OPT(n, W)$.

We have that, if $I_n$ is included in the optimum solution,

$OPT (n, W) = w_n + OPT (n-1, W-w_n)$.

Case 2:

If $I_n$ is not included in the optimum solution, then we have that:

$OPT (n, W) = OPT (n-1, W)$.

—-

Generalizing the above, we have that, for $1 \leq i \leq n$ and $0 \leq w \leq W$:

$OPT ( i, w) = OPT (i-1, w)$ [if $w_i > w$]

Else,

$OPT (i, w) = max \{ w_i + OPT (i-1, w- w_i), OPT (i-1, w) \}$

—-

Also, $OPT (0, w) = 0$ for all $w$.

—-

Pseudocode for computing the optimum value:

Based on the above recurrence, we can construct an algorithm.

For i from 1 to n:

For w from 0 to W:

Compute OPT[i,w] using the above recurrence.

End.

—-

The above code runs in $O(nW)$ time [since O(1) time is spent for computing each OPT[i,w] value].

—-

Computing the Optimum solution:

We can compute the optimum solution recursively given the table of OPT[i,w] values.

Function: Print_OPT (k, w)

If $k == o$

Return;  //Breaking the recursion. We can also have the condition as $k == 0$ OR $w == 0$

If $w_k > w$

Print_OPT (k-1, w);

Else if $w_k + OPT (k-1, w-w_k) > OPT (k-1, w)$

Print_OPT (k-1, w- w_k);

Print $I_k$

Else

Print_OPT (k-1, w);

End of function.

The optimum solution is printed on calling Print_OPT (n, W). The time taken is O(n).

—-