logging in or signing up THE GREEDY METHOD ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 6074 Category: Education License: All Rights Reserved Like it (11) Dislike it (0) Added: March 06, 2009 This Presentation is Public Favorites: 4 Presentation Description No description available. Comments Posting comment... By: karthickklr (4 month(s) ago) this PPT useful and allow me to download this PPT Saving..... Post Reply Close Saving..... Edit Comment Close By: baljit89 (9 month(s) ago) plz allow me to download this presentation..... Saving..... Post Reply Close Saving..... Edit Comment Close By: m.gopal92 (12 month(s) ago) hi pls mail this ppt m.gopal92@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: sureshkrishnan (13 month(s) ago) i want to download this ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: fudu (15 month(s) ago) i wana to download to this Saving..... Post Reply Close By: bhuvaneswarikombaiah (2 month(s) ago) i want to download this ppt Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript THE GREEDY METHOD : THE GREEDY METHOD The greedy method can be applied to a variety of problems which have n inputs. The goal is to obtain a subset that satisfies some constraints. Any subset (of inputs) that satisfies the constraints is known as feasible solution. A feasible solution that maximizes or minimizes a given objective function is an optimal solution. There is an obvious way to find a feasible solution, but not an optimal one. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Procedure Greedy (A,n) //A (1:n) contains n inputs // solution ? Ø for i? 1 to n do x ? SELECT (A) if feasible (solution, x) then solution ? union (solution, x) end if repeat return ( solution) END GREEDY THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Knapsack Problem Given n objects with weights (w1,….wn) a knapsack with capacity M. (w1, w2,wn) <=M. If a fraction of an object, say xi is placed in knapsack, a profit pixi is made objective: To fill the knapsack with objects that maximizes the profit. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Formulation of the problem: Maximize ?pixi …… (1) subject to 1?i?n ?wixi ? M …….. (2) 1 ? i ? n and 0 ? xi ? 1 1? x ? n …….(3) profits and weights at position . A feasible solution is any solution satisfying (2) and (3). An optimal solution is a feasible one for which (1) is maximum. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: N=3, M=20 (p1,p2,p3) : (25,24,15); (w1, w2, w3) = (18, 15, and 10) (x1, x2, x3 ? wixi ? pixi (1) (1/2, 1/3, 1/4) 9+5+2.5=16.5 12.5+8+3.75=24.25 (2) (1, 2/5, 0) 18+2+0=20 25+3.2+0=28.2 (3) (0, 2/3, 1) 0+10+10=20 0+16+15=31 (4) (0, 1, 1/2) 0+15+5=20 0+24+7.5=31.5 (i), (ii), (iii), (iv) are feasible ones and (4) is the optimum one. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Observations about greedy method Generally w1+w2+……+wn ? M; But if ?wi = M then xi =1. 1= i = n is an optional solution (not a fraction of w; but whole wi is considered =1 (not a fraction of wi but whole wi is considered ? xi = 1) 2) If ?wi > M than all xi cannot be 1 ? xi 0 = xi < 1. 3) All optional solutions will fill the knapsack exactly, as some fractional amount can be placed till ?wi = M . THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Strategies for feasible solutions whose sum is M First method : Consider the objects in the non-increasing order of profits. Example: (p1, p2, p3) = (25, 24, 15); (w1, w2, w3) = (18, 15, 10) M= 20 profit is maximum for the first item ? x1= 1 Remaining weight 20-18= 2 x2 = 2/15 because 2/15 of w2 = 15 =2 THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ?The solution is (x1, x2, x3) = (1, 2/15, 0) and the profit is 25+24 x 2/15 = 25+48/15 = 25 + 3.2 = 28.2. This is solution (iii) (in slide No. 5) which is feasible but not optimal. Second method: Use the capacity as slowly as possible or consider the objects in the non decreasing order of weights. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: For the above example (in slide No. 5) First consider third item x3 = 1 Remaining weight is 20 – 10 =10 15x2 = 10 or x2 =10/15 = 2/3 and x1= 0 (0, 2/3, 1) is the solution with profit ?pixi = 0 + 24.2/3+15.1 = 16+15 = 31 which is feasible but not optimal solution. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Third Method: Achieve a balance between the rate at which the profit increases and the rate at which the capacity is used. This is obtained by including the object which has maximum profit per unit of capacity. Objects are included in non increasing order of the ratio pi/wi THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: (p1,p2,p3) : (25,24,15); (w1, w2, w3) = (18, 15,10) (P1/ w1, P2/ w2, P3/ w3) = (25/18, 24/15, 15/10) = 1.38, 1.6, 1.5 M = 20 x2 = 1 M = 20-15 = 5 x3 = 5/10 = ½ x1 = 0 ? (0,1,1/2) is the solution with profit ? pixi which is also optimal Algorithm for GREDY- KNAPSACK THE GREEDY METHOD(Contd..) : THE GREEDY METHOD(Contd..) Procedure Greedy Knapsack (P, W, M, X, n) // p (1: n), W (1:n) are the profits and weights respectively // // of the n objects // real P(1:n),W(1:n),X(1:n); integer i,n x?0 cu = M // cu is the remaining capacity // for i?1 to n do if w(i) > cu then exit endif x(i) ? 1 cu ? cu-w (i) repeat if = n then x (i)? cu/w(I) endif end GREEDY-KNAPSACK THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Theorem: Let X=(x1, x2….., x3) be the solution generated by GREEDY KNAPSACK. If p1/w1 = p2/w2 = pn/wn then the algorithm generated an optional solution to the given algorithm generates an optional solution to the given instance of the knapsack problem. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) PROOF: Let x= (x1, x2, --------, xn) be the solution generated by greedy knapsack. If x1=1, x2=1,…..xn=1 clearly x is optional. So let j be the least be the least index such that xj ?1. It follows that xi =1 for 1= I < j, xi = 0 for j < I = n and 0 = xj < 1. Let Y = (y1, y2……yn) be all optimal solution. As the optimal solution fills the knapsack exactly we may assume ?wiyi = M . THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) If x1 = y1, x2=y2,…..xn= yn, then x is also optimal. So, let k be the least index such that xk ? yk. Let us prove that yk < xk There are three possibilities k<j, k=j, k>j i) If k < j then xk = 1 as xi = 1 for 1= i<j. As yk ? xk, y < xk because yk cannot be greater than 1= xk THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ii) If k = j since Greedy Knapsack considers x such that ? wixi = M and by the definition of k yi= xi for 1=i<j=k and by definition of j 0 = xj<1 i.e xj= yk< 1. If yk> xk then ?wiyi > M which os not possible so yk< xk. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ii) If k>j yk>xk and wiyi>M which is not possible (yk>xk because j is such that 0 = xj < 1 k is such that yk ? xk k > j so xk= 0 by the definition of j yk ? 0 and xi=yi for 1=i<k>j so yk>xk. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) So we proved that yk< xk where yk ? xk and yk= xk such that 1=i <k Suppose we increase yk to xk and decrease as many of (yk+1…..yn) as is necessary so that the total capacity used is still M. Let us call this new solution. Z = (z1,….., zn) with zi=xi 1=i<k and ?wi (yi-zi) ? wk(zk - yk) ? pizi = ?piyi + ( zk-yk) wk pk/wk - ?(yi-zi) wi pi/wi 1=i=n 1=i=n k=i=n THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) It is given in theorem that pi/wi = pi + 1/wi+1 1=i=n-1 ? -pi/wi = -pi+1/wi+1 hence pk/wk = pi/wi for k<i=n and so –pk/wk = pi/wi for k<i=n and hence –pi/wi = - pk/wk 0=i=n ?pizi = ?piyi + [(zk-yk)wk - ?(yi-zi)wi] pk/wk = 0 by (1) ? ?pizi = ?piyi If ?pizi > ?piyi then Y could not have been as optimal. If ?piz i= ?piyi then either Z=x or Z?x If Z=x, because Z=Y, so Y=X and X is optimal THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Suppose Z ? X then least index in which Y and X differ is increased by 1. Repeated use of the above argument will either show that Y is not optimal or will transfer Y into X. ?So, X is also optimal. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
THE GREEDY METHOD ankush85 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 6074 Category: Education License: All Rights Reserved Like it (11) Dislike it (0) Added: March 06, 2009 This Presentation is Public Favorites: 4 Presentation Description No description available. Comments Posting comment... By: karthickklr (4 month(s) ago) this PPT useful and allow me to download this PPT Saving..... Post Reply Close Saving..... Edit Comment Close By: baljit89 (9 month(s) ago) plz allow me to download this presentation..... Saving..... Post Reply Close Saving..... Edit Comment Close By: m.gopal92 (12 month(s) ago) hi pls mail this ppt m.gopal92@gmail.com Saving..... Post Reply Close Saving..... Edit Comment Close By: sureshkrishnan (13 month(s) ago) i want to download this ppt Saving..... Post Reply Close Saving..... Edit Comment Close By: fudu (15 month(s) ago) i wana to download to this Saving..... Post Reply Close By: bhuvaneswarikombaiah (2 month(s) ago) i want to download this ppt Saving..... Edit Comment Close loading.... See all Premium member Presentation Transcript THE GREEDY METHOD : THE GREEDY METHOD The greedy method can be applied to a variety of problems which have n inputs. The goal is to obtain a subset that satisfies some constraints. Any subset (of inputs) that satisfies the constraints is known as feasible solution. A feasible solution that maximizes or minimizes a given objective function is an optimal solution. There is an obvious way to find a feasible solution, but not an optimal one. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Procedure Greedy (A,n) //A (1:n) contains n inputs // solution ? Ø for i? 1 to n do x ? SELECT (A) if feasible (solution, x) then solution ? union (solution, x) end if repeat return ( solution) END GREEDY THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Knapsack Problem Given n objects with weights (w1,….wn) a knapsack with capacity M. (w1, w2,wn) <=M. If a fraction of an object, say xi is placed in knapsack, a profit pixi is made objective: To fill the knapsack with objects that maximizes the profit. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Formulation of the problem: Maximize ?pixi …… (1) subject to 1?i?n ?wixi ? M …….. (2) 1 ? i ? n and 0 ? xi ? 1 1? x ? n …….(3) profits and weights at position . A feasible solution is any solution satisfying (2) and (3). An optimal solution is a feasible one for which (1) is maximum. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: N=3, M=20 (p1,p2,p3) : (25,24,15); (w1, w2, w3) = (18, 15, and 10) (x1, x2, x3 ? wixi ? pixi (1) (1/2, 1/3, 1/4) 9+5+2.5=16.5 12.5+8+3.75=24.25 (2) (1, 2/5, 0) 18+2+0=20 25+3.2+0=28.2 (3) (0, 2/3, 1) 0+10+10=20 0+16+15=31 (4) (0, 1, 1/2) 0+15+5=20 0+24+7.5=31.5 (i), (ii), (iii), (iv) are feasible ones and (4) is the optimum one. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Observations about greedy method Generally w1+w2+……+wn ? M; But if ?wi = M then xi =1. 1= i = n is an optional solution (not a fraction of w; but whole wi is considered =1 (not a fraction of wi but whole wi is considered ? xi = 1) 2) If ?wi > M than all xi cannot be 1 ? xi 0 = xi < 1. 3) All optional solutions will fill the knapsack exactly, as some fractional amount can be placed till ?wi = M . THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Strategies for feasible solutions whose sum is M First method : Consider the objects in the non-increasing order of profits. Example: (p1, p2, p3) = (25, 24, 15); (w1, w2, w3) = (18, 15, 10) M= 20 profit is maximum for the first item ? x1= 1 Remaining weight 20-18= 2 x2 = 2/15 because 2/15 of w2 = 15 =2 THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ?The solution is (x1, x2, x3) = (1, 2/15, 0) and the profit is 25+24 x 2/15 = 25+48/15 = 25 + 3.2 = 28.2. This is solution (iii) (in slide No. 5) which is feasible but not optimal. Second method: Use the capacity as slowly as possible or consider the objects in the non decreasing order of weights. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: For the above example (in slide No. 5) First consider third item x3 = 1 Remaining weight is 20 – 10 =10 15x2 = 10 or x2 =10/15 = 2/3 and x1= 0 (0, 2/3, 1) is the solution with profit ?pixi = 0 + 24.2/3+15.1 = 16+15 = 31 which is feasible but not optimal solution. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Third Method: Achieve a balance between the rate at which the profit increases and the rate at which the capacity is used. This is obtained by including the object which has maximum profit per unit of capacity. Objects are included in non increasing order of the ratio pi/wi THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Example: (p1,p2,p3) : (25,24,15); (w1, w2, w3) = (18, 15,10) (P1/ w1, P2/ w2, P3/ w3) = (25/18, 24/15, 15/10) = 1.38, 1.6, 1.5 M = 20 x2 = 1 M = 20-15 = 5 x3 = 5/10 = ½ x1 = 0 ? (0,1,1/2) is the solution with profit ? pixi which is also optimal Algorithm for GREDY- KNAPSACK THE GREEDY METHOD(Contd..) : THE GREEDY METHOD(Contd..) Procedure Greedy Knapsack (P, W, M, X, n) // p (1: n), W (1:n) are the profits and weights respectively // // of the n objects // real P(1:n),W(1:n),X(1:n); integer i,n x?0 cu = M // cu is the remaining capacity // for i?1 to n do if w(i) > cu then exit endif x(i) ? 1 cu ? cu-w (i) repeat if = n then x (i)? cu/w(I) endif end GREEDY-KNAPSACK THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Theorem: Let X=(x1, x2….., x3) be the solution generated by GREEDY KNAPSACK. If p1/w1 = p2/w2 = pn/wn then the algorithm generated an optional solution to the given algorithm generates an optional solution to the given instance of the knapsack problem. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) PROOF: Let x= (x1, x2, --------, xn) be the solution generated by greedy knapsack. If x1=1, x2=1,…..xn=1 clearly x is optional. So let j be the least be the least index such that xj ?1. It follows that xi =1 for 1= I < j, xi = 0 for j < I = n and 0 = xj < 1. Let Y = (y1, y2……yn) be all optimal solution. As the optimal solution fills the knapsack exactly we may assume ?wiyi = M . THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) If x1 = y1, x2=y2,…..xn= yn, then x is also optimal. So, let k be the least index such that xk ? yk. Let us prove that yk < xk There are three possibilities k<j, k=j, k>j i) If k < j then xk = 1 as xi = 1 for 1= i<j. As yk ? xk, y < xk because yk cannot be greater than 1= xk THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ii) If k = j since Greedy Knapsack considers x such that ? wixi = M and by the definition of k yi= xi for 1=i<j=k and by definition of j 0 = xj<1 i.e xj= yk< 1. If yk> xk then ?wiyi > M which os not possible so yk< xk. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) ii) If k>j yk>xk and wiyi>M which is not possible (yk>xk because j is such that 0 = xj < 1 k is such that yk ? xk k > j so xk= 0 by the definition of j yk ? 0 and xi=yi for 1=i<k>j so yk>xk. THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) So we proved that yk< xk where yk ? xk and yk= xk such that 1=i <k Suppose we increase yk to xk and decrease as many of (yk+1…..yn) as is necessary so that the total capacity used is still M. Let us call this new solution. Z = (z1,….., zn) with zi=xi 1=i<k and ?wi (yi-zi) ? wk(zk - yk) ? pizi = ?piyi + ( zk-yk) wk pk/wk - ?(yi-zi) wi pi/wi 1=i=n 1=i=n k=i=n THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) It is given in theorem that pi/wi = pi + 1/wi+1 1=i=n-1 ? -pi/wi = -pi+1/wi+1 hence pk/wk = pi/wi for k<i=n and so –pk/wk = pi/wi for k<i=n and hence –pi/wi = - pk/wk 0=i=n ?pizi = ?piyi + [(zk-yk)wk - ?(yi-zi)wi] pk/wk = 0 by (1) ? ?pizi = ?piyi If ?pizi > ?piyi then Y could not have been as optimal. If ?piz i= ?piyi then either Z=x or Z?x If Z=x, because Z=Y, so Y=X and X is optimal THE GREEDY METHOD (Contd..) : THE GREEDY METHOD (Contd..) Suppose Z ? X then least index in which Y and X differ is increased by 1. Repeated use of the above argument will either show that Y is not optimal or will transfer Y into X. ?So, X is also optimal.