Differences

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

--- courses:cs211:winter2012:journals:garrett:entries:week_9 [2012/03/28 03:45] – 6.3 garrettheath4
+++ courses:cs211:winter2012:journals:garrett:entries:week_9 [2012/03/28 04:04] (current) – made ratings a table garrettheath4
@@ Line 2: / Line 2: @@
 ===== Chapter Scores =====
-  * **Readability Score**: FIXME / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_2.png?100|}}
+| **Readability Score** | 6 / 10 | {{:courses:cs211:winter2012:journals:garrett:entries:rating_3.png?nolink&100|}} |
-  * **Interest Score**: FIXME / 10 {{:courses:cs211:winter2012:journals:garrett:entries:rating_3_5.png?100|}}
+|  **Interest Score** | 8 / 10 | {{:courses:cs211:winter2012:journals:garrett:entries:rating_4.png?nolink&100|}} |
 ===== Readings =====
@@ Line 23: / Line 23: @@
 === 6.4: Subset Sums and Knapsacks ===
+The **knapsack problem** is a problem in which we have ''n'' items, each of which has a weight (''w>0'') and a value (''v>0'').  If we have a knapsack with a capacity of ''W'' kilograms, how can we fill the knapsack so we can maximize the total value?
+We go about solving this problem much like we did with the weighted interval scheduling problem in that we have to make a **binary** decision to include an item in the solution or not.  Unlike weighted interval scheduling, however, items with equal or less weight do not conflict with each other, so we can't stop our algorithm just because we choose an item, we have to keep going to make sure we consider all reasonable combinations.  We use a **weight limit** to designate the amount of weight we can still add to the knapsack after adding previous items.  The ongoing weight limit to determine whether or not to include an item.