# THE GREEDY METHOD

Published on March 6, 2009

Author: ankush85

Source: authorstream.com

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.

03. 04. 2009
0 views

06. 03. 2009
0 views

27. 03. 2009
0 views

20. 11. 2009
0 views

22. 11. 2009
0 views

14. 07. 2009
0 views

18. 03. 2009
0 views

08. 04. 2009
0 views

06. 03. 2009
0 views

20. 04. 2009
0 views

03. 06. 2013
0 views

03. 06. 2013
0 views

16. 10. 2012
0 views

25. 09. 2012
0 views

25. 09. 2012
0 views

03. 01. 2012
0 views

24. 11. 2009
0 views

22. 11. 2009
0 views

22. 11. 2009
0 views

16. 05. 2009
0 views

19. 04. 2009
0 views

16. 05. 2009
0 views

10. 07. 2009
0 views

01. 07. 2009
0 views

21. 07. 2009
0 views

21. 07. 2009
0 views

01. 07. 2009
0 views

05. 03. 2009
0 views

13. 06. 2009
0 views

11. 05. 2009
0 views

05. 03. 2009
0 views

06. 03. 2009
0 views

25. 08. 2009
0 views

19. 06. 2009
0 views

24. 06. 2009
0 views

02. 10. 2008
0 views

25. 04. 2009
0 views

28. 04. 2009
0 views

17. 06. 2009
0 views

25. 04. 2009
0 views

25. 06. 2009
0 views

19. 06. 2009
0 views

18. 03. 2009
0 views

27. 04. 2009
0 views

23. 03. 2009
0 views

23. 05. 2009
0 views

23. 05. 2009
0 views

24. 06. 2009
0 views

24. 05. 2009
0 views

03. 04. 2009
0 views

08. 04. 2009
0 views

23. 03. 2009
0 views

06. 03. 2009
0 views

29. 04. 2009
0 views

24. 05. 2009
0 views

06. 03. 2009
0 views

11. 04. 2009
0 views

08. 03. 2009
0 views

13. 03. 2009
0 views

04. 09. 2009
0 views

20. 11. 2009
0 views

22. 11. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

21. 04. 2009
0 views

25. 05. 2009
0 views

06. 03. 2009
0 views

05. 03. 2009
0 views

14. 07. 2009
0 views

14. 07. 2009
0 views

05. 03. 2009
0 views

09. 05. 2009
0 views

05. 03. 2009
0 views

05. 03. 2009
0 views

05. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

06. 03. 2009
0 views

09. 03. 2009
0 views

09. 03. 2009
0 views

13. 03. 2009
0 views

19. 03. 2009
0 views

25. 03. 2009
0 views

08. 04. 2009
0 views

10. 04. 2009
0 views

10. 04. 2009
0 views

13. 04. 2009
0 views

15. 04. 2009
0 views

17. 04. 2009
0 views

23. 04. 2009
0 views

21. 04. 2009
0 views

21. 04. 2009
0 views

21. 04. 2009
0 views

23. 04. 2009
0 views

25. 04. 2009
0 views

25. 04. 2009
0 views

29. 04. 2009
0 views

29. 04. 2009
0 views

26. 04. 2009
0 views

26. 04. 2009
0 views

27. 04. 2009
0 views

05. 05. 2009
0 views

14. 05. 2009
0 views

16. 05. 2009
0 views

15. 05. 2009
0 views

15. 05. 2009
0 views

23. 04. 2009
0 views

23. 05. 2009
0 views

23. 05. 2009
0 views

24. 05. 2009
0 views

28. 05. 2009
0 views

04. 06. 2009
0 views

19. 06. 2009
0 views

19. 06. 2009
0 views

07. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

13. 06. 2009
0 views

15. 06. 2009
0 views

26. 06. 2009
0 views

27. 06. 2009
0 views

01. 07. 2009
0 views

06. 07. 2009
0 views

05. 07. 2009
0 views

05. 07. 2009
0 views

10. 07. 2009
0 views

01. 08. 2009
0 views

26. 04. 2009
0 views

21. 08. 2009
0 views

25. 08. 2009
0 views

27. 08. 2009
0 views

27. 08. 2009
0 views

27. 08. 2009
0 views

04. 09. 2009
0 views

04. 09. 2009
0 views

27. 06. 2009
0 views