Chapter 6.4: Subset Sums and Knapsacks

This problem is a little different from the previous dynamic programming problems we've seen before. Here, we are given n items, each with a nonnegative weight, w_i (for i=1,…,n). There is also a bound W. Our goal is to select a subset S of items so that the total weight of the items does not exceed W, while at the same time maximizing the total weight of the items we choose. This is considered a subset sum problem. It is a special case of the knapsack problem, where each of the n items also has an associated value v_i and the goal is to maximize both total weight (within W) and total value.

In order to deal with the total weight and the upper bound parameters in this problem, our subproblems (and thus our recursive call) is going to have to address both at the same time. So, if an item is in the optimal solution, we must look at the remaining items under the condition that W has decreased by the weight of the item we've already chosen. If an item is not in the solution, then we can just look at the smaller problem without considering that item. In other words, the algorithm looks like this: Subset-Sum(n,W):

• M[0…n, 0…W]
• Initialize M[0,w]=0 for each w=0,1,…,W
• for i=1,2,…,n:
• ⇒for w=0,…,W:
• if w<w_i then Opt(i,w)=Opt(i-1,W)
• else: Opt(i,w)=max(w_i+Opt(i-1,w-w_i), Opt(i-1,w))
• return M[n,W]

This algorithm runs in pseudo-polynomial time: O(nW). It is efficient for relatively small values of W, but not so efficient as W gets large.

Tracing back through the optimal values of the subproblems will give you the optimal set S, which can be done in O(n) time. The knapsack problem is similar.

I would rate this section an 8. I didn't really see much difference in the algorithms for the subset sum problem and the knapsack problem (if there is a difference) so I wish that was a little clearer. Other than that, everything was comprehensible!