Dynamic Programming – 3 : Subset Sum

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

—-