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

—-


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: