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 j i) If k < j then xk = 1 as xi = 1 for 1= i

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 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 j so xk= 0 by the definition of j yk ? 0 and xi=yi for 1=ij 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

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 ?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.