Greedy works for denominations10, 5, and 1 (Fun part, not tested)Theorem: The greedy algorithm works for denominations: 10, 5 and 1.Proof:We compare × and ×x'(# of 10o dollar coins),(y and y)# of 5 dollarcoins and (z and z') # of 1 dollar coins, one by one.Comparison of x and x.Since x'is from greedy algorithm,x'zx.If x>x, then yx5+ z ×1 ≥10. (because × × 10+ yx5+ z ×1 = x'× 10+yx5+z'x1)Thus, we can modify the optimal solution (x, y, z) using one more 10dollarcointoreplace1odollarsthatareexpressedby(1)two5dollar coins, (2)one 5 dollar coin +five 1 dollar coins or (3)ten 1 dollarcoins.The new solution (x+1,y",z)contains less# of coins than (x,Yz)Contradiction!Because byassumption,(x,y,z)is optimum..Thus,x'x cannotbetrue.Therefore,x'=x.Similarly,wecan showy'=yandz=z
Greedy works for denominations 10, 5, and 1 (Fun part, not tested) Theorem: The greedy algorithm works for denominations: 10, 5 and 1. § Proof: § We compare x and x’ (# of 10 dollar coins), (y and y ’) # of 5 dollar coins and (z and z ’) # of 1 dollar coins, one by one. § Comparison of x and x’. l Since x’ is from greedy algorithm, x’x. l If x’>x, then y5+ z 1 10. (because x 10+ y5+ z 1 = x’ 10+y ’ 5+ z ‘ 1 ) l Thus, we can modify the optimal solution (x, y, z) using one more 10 dollar coin to replace 10 dollars that are expressed by (1) two 5 dollar coins, (2) one 5 dollar coin +five 1 dollar coins or (3) ten 1 dollar coins. l The new solution (x+1, y ’’, z ’’) contains less # of coins than (x, y, z). l Contradiction! Because by assumption, (x, y, z) is optimum. l Thus, x’>x cannot be true. Therefore, x’ =x. § Similarly, we can show y ’ =y and z ’ =z
Strange denominations:- 7 dollars, 5 dollars and 1 dollars Greedy algorithm for 11 dollars:.7dollars+4 ×1 dollar=11 dollars.(5 coins arerequired.)Abetterway:2x5dollars+1dollar=11dollars(3 coins are required)Sometimes the greedy algorithm does notwork
Strange denominations: § 7 dollars, 5 dollars and 1 dollars § Greedy algorithm for 11 dollars: l 7dollars+4 1 dollar=11 dollars. (5 coins are required.) § A better way: 2 5 dollars +1 dollar=11 dollars. (3 coins are required) § Sometimes the greedy algorithm does not work
The O-1 Knapsack problem: The O-1 knapsack problem:Nitems,wherethei-thitemisworthv;dollarsand weight w,pounds.V;and w;areintegersA thief can carry at most W (integer) poundsHowtotakeasvaluablea loadaspossibleAn item cannot be divided into pieces.The fractional knapsack problem:The same setting,but the thief can take fractions of items
The 0-1 Knapsack problem: § The 0-1 knapsack problem: § N items, where the i-th item is worth vi dollars and weight wi pounds. l vi and wi are integers. § A thief can carry at most W (integer) pounds. § How to take as valuable a load as possible. l An item cannot be divided into pieces. § The fractional knapsack problem: § The same setting, but the thief can take fractions of items
Solve the fractional Knapsack problem: Greedy on the value per pound vi/wi..Eachtime,taketheitemwithmaximumvi/wi..If exceeds W.take fractions of the item.Proof of correctness: (The hard part)LetX =ii,iz, ...ikbetheoptimal itemstaken.Considertheitemjwith thehighest v, /w;if jisnot used inX (the optimal solution),get rid of some items(possiblyfractionalitems)andadditemj.(sincefractionalitemsareallowed,wecandoit.).Total valueis increased..One more item selected by greedy isadded toXRepeat the process, X is changed to contain all items selected bygreedy WITHOUT decreasing the total value taken by the thief
Solve the fractional Knapsack problem: § Greedy on the value per pound vi/wi. l Each time, take the item with maximum vi/wi . l If exceeds W, take fractions of the item. § Proof of correctness: (The hard part) § Let X = i1 , i2 , .ik be the optimal items taken. § Consider the item j with the highest vi /wi. § if j is not used in X (the optimal solution), get rid of some items (possibly fractional items) and add item j. (since fractional items are allowed, we can do it.) l Total value is increased. l One more item selected by greedy is added to X § Repeat the process, X is changed to contain all items selected by greedy WITHOUT decreasing the total value taken by the thief
The O-1 knapsack problem cannotbe solved optimally by greedyCounterexample:(moderatepart)W=10Items found (6pounds,12dollars),(5pounds,9 dollar),(5pounds, 9 dollars), (3pounds, 3 dollars), (3 pounds, 3dollars)If we first take (6,12)according to greedy algorithm,then solution is (6,12),.(3,3)(total value is 12+3=15)However, a better solution is (5, 9), (5, 9) with totalvalue 18.To show that a statement does not hold, we only have to giveanexampleTo show that the theorem is true, we have to give an proof
The 0-1 knapsack problem cannot be solved optimally by greedy § Counter example: (moderate part) § W=10 § Items found (6pounds, 12dollars), (5pounds, 9 dollar), (5pounds, 9 dollars), (3pounds, 3 dollars), (3 pounds, 3 dollars) § If we first take (6, 12) according to greedy algorithm, then solution is (6, 12), (3, 3) (total value is 12+3=15). § However, a better solution is (5, 9), (5, 9) with total value 18. To show that a statement does not hold, we only have to give an example. To show that the theorem is true, we have to give an proof