Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioniv [2012/03/28 02:54] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptersixsectioniv [2012/03/28 03:13] (current) – [Designing the Algorithm] mugabej
@@ Line 21: / Line 21: @@
 \\
 ** Better solution**
+>>>>>>>>>>>>>>>>>>> OPT(i, w) = max profit subset of items 1,..., i with weight limit w\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 1: OPT does not select item i:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT selects best of { 1, 2, …, i-1 } using weight limit w\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Case 2: OPT selects item i:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> new weight limit = w – w<sub>i</sub> \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT selects best of { 1, 2, …, i–1 } using new weight limit, w – w<sub>i</sub>\\
+>>>>>>>>>>>>>>>>>>> So, OPT(i,w) is:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 0 if i =0\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> OPT(i-1,w) if w<sub>i</sub> > w\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> max{OPT(i-1,w), v<sub>i</sub> + OPT(i-1,w-w<sub>i</sub>)} otherwise\\
+\\
+====== Algorithm ======
+>>>>>>>>>>>>>>>>>>> Input: N, w<sub>1M/sub>,…,w<sub>N</sub>, v<sub>1</sub>,…,v<sub>N</sub>\\
+>>>>>>>>>>>>>>>>>>> for w = 0 to W: O(W) time\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[0, w] = 0\\
+>>>>>>>>>>>>>>>>>>> for i = 1 to N: --> For all items\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for w = 1 to W: --> For all possible weights( So O(NW) time\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if w<sub>i</sub> > w : --> item's weight is more than available\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[i, w] = M[i-1, w]\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> else:\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> M[i, w] = max{ M[i-1, w], vi + M[i-1, w-wi] }\\
+>>>>>>>>>>>>>>>>>>> return M[n,W]
+** Algorithm Analysis**
+\\
+  * The algorithm takes Θ(nW) time to compute the optimal value of the problem.
+  * Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time.
+  * Thus the Knapsack Problem can be solved in O(nW) time.
+I give this section an 8/10.