## Dynamic Programming – 3 : Subset Sum

February 3, 2011 Leave a comment

**Subset Sum **

We are given items , each having non-negative integral weight . We are also given a non-negative integral weight bound . 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 is one such that the total weight of items in is at most .

**Solution. **

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

**Case 1: **

If is included in the optimum solution, the optimum solution would be plus the optimum solution obtained from the set of items with the weight bound as .

**Notation: **Let OPT (i, w) denote the value of the optimum solution obtained on the set with weight bound .The original task, then, is to compute .

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

.

**Case 2: **

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

.

—-

Generalizing the above, we have that, for and :

[if ]

Else,

—-

Also, for all .

—-

**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 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 **

**Return; //Breaking the recursion. We can also have the condition as ** OR

**If **

**Print_OPT (k-1, w); **

**Else if **

**Print_OPT (k-1, w- w_k); **

**Print **

**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).

—-