Differences

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

--- courses:cs211:winter2014:journals:emily:entryeight [2014/03/26 02:16] – [Chapter 6.4] hardye
+++ courses:cs211:winter2014:journals:emily:entryeight [2014/03/26 03:04] (current) – [Chapter 6.4] hardye
@@ Line 158: / Line 158: @@
 **Subset Sums and Knapsacks: Adding a Variable**
+In this section we solve a problem that has duration and deadline but not have an interval by which they need to be done. The problem we are considering is a machine that processes a set of requests 1 through n where we can only use the machine from 0 to W and each job has a process time w<sub>i</sub>. We want to choose the jobs that use the machine as much as possible up to the time W. We can make this problem more general into the knapsack problem where each request has a value and a weight and we want to chose a subset of maximum total value that does not exceed the weight W of the knapsack. We cannot use a greedy approach to solve this problem!
+**The Algorithm:**
+One way we could try the algorithm is to consider the first i requests but this does not work. We need more subproblems. To find opt(n) we need the value of opt(n-1) and the best solution of subset n-1 and total allowed weight W-w<sub>n</sub>. Opt(i,w) will be the value of the optimal solution of a subset 1 through i with maximum allowed weight w. If n is not in the solution then opt(n,W) = opt(n-1,W). If n is in the solution then opt(n,W) = w<sub>n</sub> + opt(n-1, W-w<sub>n</sub>). When W is less than w<sub>n</sub> then n cannot be in the solution.
+    Subset-Sum(n,W)
+      Array 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
+          M[i,w] = opt(i,w) = max(opt(i-1, w),w(i) + opt(i-1,w-w(i))
+        Endfor
+      Endfor
+      Return M[n, W]
+We prove the algorithms correctness by induction. Instead of a single array, we use a matrix of subproblems to build up the values. We compute each of the values in M in constant time so the runtime is the number of entries in M which is O(nW). It is a polynomial function of n and W, not just n. This is //pseudo-polynomial//. To get the set of items and not just the value we trace back through the array as we did in previous problems. This can be found in O(n) time.
+This section was really interesting to me and seems like something really practical and would be used a lot. I thought like the previous section it cut out a lot of the in depth descriptions but it was a little more easy to read because I understood it better with more experience. Readability 8/10