Differences

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

--- courses:cs211:winter2012:journals:ian:chapter6 [2012/03/28 04:16] – 6.3 sturdyi
+++ courses:cs211:winter2012:journals:ian:chapter6 [2012/03/28 04:27] (current) – sturdyi
@@ Line 20: / Line 20: @@
    * No comments.
    * No complaints.
+====== 6.4 Subset Sums and Knapsacks ======
+   * The knapsack problem is the selection of a subset (without replacement) of values that has sum as close as possible to a target. Here one cannot recurse merely over items, since unlike in weighted interval schedule the subproblems for a given choice are not independent of the choices already made (they affect the target). Therefore, one needs to define subproblems in two variables, the set of goods to be considered and the weight still to fill (but one can still make the choice sequentially, so that there are n sets defined by their greatest element). Total running time is O(nW), the result of filling in nW matrix entries in O(1) time each. The knapsack problem is a generalization, maximizing the sum of value subject to a weight constraint. However, the same recurrence holds, with merely a different definition of optimality, and it can also be solved in O(nW).
+   * No questions.
+   * No insights.
+   * Again with the introduction of the false starts first? I can see their reasons, but still do not much like it.