Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:virginia:chapter6 [2012/03/26 04:51] – lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter6 [2012/03/26 04:53] (current) – [Section 4: Subset Sums and Knapsacks] lovellv
@@ Line 29: / Line 29: @@
 ===== Section 4: Subset Sums and Knapsacks =====
-In this section we consider the Knapsack problem: we have a knapsack that can carry a weight of W.  We also have some items with different weights and values.  We want the maximize the value of the objects we put in our knapsack, without going over the weight limit.  We will first consider the simpler case of this problem where each item's value is the same.  This problem is similar to the weighted interval problem (we know we either want an item or we don't), but we need an extra variable to keep track of the weight remaining in the bag so we use Opt(i,w) to denote the weight of the optimal solution considering items 1 through i with max weight allowed w.  This gives us a recurrence of Opt(i,w) = max[opt(i-1, w), w(i) + opt(i-1, w - w(i)].  The first option indicates we didn't choose i, the second indicates we did so we reduced the available weight by the weight of i.  Of course if w(i) > w, then we cannot choose it and we have Opt(i, w) = Opt(i-1, w).  This algorithm fills a two-dimensional array of size n by W and thus computes the optimal weight in O(nW) time.  From the filled array, we can then find the items we should include in O(n) time.
+In this section we consider the Knapsack problem. We have a knapsack that can carry a weight of W.  We also have some items with different weights and values.  We want to maximize the value of the objects we put in our knapsack, without going over the weight limit.
+We will first consider the simpler case of this problem where each item's value is the same.  This problem is similar to the weighted interval problem (we know we either want an item or we don't), but we need an extra variable to keep track of the weight remaining in the bag. Thus we use Opt(i,w) to denote the weight of the optimal solution considering items 1 through i with max weight allowed w.  This gives us a recurrence of Opt(i,w) = max[opt(i-1, w), w(i) + opt(i-1, w - w(i)].  The first option indicates we didn't choose i, the second indicates we did so we reduced the available weight by the weight of i.  Of course if w(i) > w, then we cannot choose it and we have Opt(i, w) = Opt(i-1, w).  This algorithm fills a two-dimensional array of size n by W and thus computes the optimal weight in O(nW) time.  From the filled array, we can then find the items we should include in O(n) time.
 In the general case where each object has a distinct value v(i), the recurrence becomes Opt(i,w) = max[opt(i-1, w), v(i) + opt(i-1, w - w(i)], again with Opt(i, w) = Opt(i-1, w) if w(i) > w.  The run time is the same.