Differences

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

--- courses:cs211:winter2014:journals:shannon:chapter6 [2014/03/25 04:18] – [Section 6.3: Segmented Least Squares: Multi-way Choices] nollets
+++ courses:cs211:winter2014:journals:shannon:chapter6 [2014/03/25 04:59] (current) – [Section 6.4: Subset Sums and Knapsacks: Adding a Variable] nollets
@@ Line 32: / Line 32: @@
 I would give this section a 7/10 as it was a little confusing at first to understand the type of subproblem we needed to divide this problem into.
 ====Section 6.4: Subset Sums and Knapsacks: Adding a Variable====
+This section discusses the problem where we have a container with a fixed capacity and a number of items with fixed weights and values. We want to fill the container with the objects that will maximize its value. This problem cannot be solved by the "obvious" set of subproblems, so we create more subproblems.
+We create a table with an increasing bag capacity across the top and an increasing number of items down the side. This way we are able to compute the maximum value at any given capacity.
+Then, given a capacity, we are able to determine what items would give us the maximized value. The algorithm, given on page 269, or the text outlines how to generate this table and fill it in.
+This algorithm runs in O(nW) time which is pseudo-polynomial as it is not just based off of the input size n, but also off of the weight capacity W since we iterate through the possible capacities.
+A common version of this problem is the knapsack problem, which we discussed in class.
+I thought some of the discussion in class ended up being more confusing in helpful as I think some students were getting themselves lost. However, the book helped make everything very clear. So did running through the complete example in class.
+I would give this section a 8/10 because I think this is a cool problem and I can think of real world applications for the algorithm which makes working through them that much easier!