THE GREEDY METHOD

50 %
50 %
Education

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.

 User name: Comment:

Kevin Durant Jersey | 20/10/16
Magento exp
nike dunk | 26/10/16
3 or more. They usually are really serious about what you may provide. But other focus prevent these people from obtaining NOW. nike dunk http://runningshoes-shop.com/11-nike-dunk
white nike shoes | 26/10/16
Journey to the coronary heart involving hockey's very best team is usually covered with gravel as well as clouded throughout airborne dirt and dust. [url=http://runningshoes-shop.com/nike-air-max-1-mens/97-men-s-new-fashion-nike-air-max-87-shoes-all-white.html]white nike shoes[/url]
blackhawks authentic jersey | 28/10/16
Bob Pavlica is definitely originally via northwest Oh and also Zach Baumgartner spent your childhood years with South Dakota. The two are big hockey enthusiasts, and also gravitated to the Nobleman upon relocating to UNA.

August 17, 2017

August 17, 2017

August 17, 2017

July 26, 2017

August 8, 2017

August 17, 2017

Related pages

The Greedy Method - Utah State University

The Greedy Method Page 1 The Greedy Method Introduction • We have completed data structures. • We now are going to look at algorithm design methods.

Greedy algorithm - Wikipedia, the free encyclopedia

Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to ...

The Greedy Method - Mutah University

The notion of "best" has to be defined in each problem separately. Therefore, the essense of each greedy algorithm is the selection policy Back to Top

The Greedy Method - Mathematics and Computer Science

The Greedy Method 4 Input: nobjects and a knapsack Each object ihas a weight w i and the knapsack has a capacity m A fraction of an object x i;0 x

Greedy-Algorithmus – Wikipedia

Greedy-Algorithmen sind oft schnell, lösen viele Probleme aber nicht optimal. Optimierungsprobleme auf Unabhängigkeitssystemen. Ein Greedy-Algorithmus ...

What is greedy algorithm? - Definition from WhatIs.com

A greedy algorithm is a mathematical process that looks for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step ...

Greedy algorithm for Egyptian fractions - Wikipedia, the ...

The greedy method leads to an expansion with ten terms, the last of which has over 500 digits in its denominator; ... Greedy algorithm for Egyptian fractions;

The Greedy Method - CMU Computer Science

The Greedy Method PGSS Computer Science Core Slides Eve: My favorite technique! Sometimes, the best way to approach a problem is to greedily take the best ...