Greedy vs Dynamic Programming ApproachGreedy Approach VS Dynamic Programming (DP)The 0/1 Knapsack problem0/1 Knapsack problemVariations of the Knapsack problemBrute force!Example with “brute force”Greedy 1: Selection criteria: Maximum beneficial item. Counter Example:Greedy 2: Selection criteria: Minimum weight item Counter Example:Greedy 3: Selection criteria: Maximum weight item Counter Example:Greedy 4: Selection criteria: Maximum benefit per unit item Counter ExampleApproximation algorithmsSlide 13Approximation ContinuedA Better Approximation AlgorithmAn Optimal Greedy Algorithm for Knapsack with Fractions (KWF)KWFExample of applying the optimal greedy algorithm for Fractional Knapsack Problem S = { ( item1 , 5, $50 ), ( item2, 20, $140 ) (item3 ,10, $60 ), }Example of applying the optimal greedy algorithm for Fractional Knapsack ProblemGreedy Algorithm for Knapsack with fractionsPrinciple of Optimality for 0/1 Knapsack problemDynamic Programming ApproachSlide 23Recursive formula for the “smaller” 0/1Knapsack Problem Using only item1 to itemi and knapsack weight at most wPseudo-code:0/1 Knapsack (n+1)*(W+1) MatrixExample: W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }Example continued W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }Example continued W = 30, S = { ( i1 , 5, $50 ), (i2 ,10, $60 ), ( i3, 20, $140 ) }Slide 29Pseudo-code Using (W +1) *2 matrixGreedy vs Dynamic Programming Approach•Comparing the methods•Knapsack problem•Greedy algorithms for 0/1 knapsack•An approximation algorithm for 0/1 knapsack•Optimal greedy algorithm for knapsack with fractions •A dynamic programming algorithm for 0/1 knapsackGreedy vs Dynamic 2Greedy Approach VS Dynamic Programming (DP)•Greedy and Dynamic Programming are methods for solving optimization problems.•Greedy algorithms are usually more efficient than DP solutions. •However, often you need to use dynamic programming since the optimal solution cannot be guaranteed by a greedy algorithm.•DP provides efficient solutions for some problems for which a brute force approach would be very slow.•To use Dynamic Programming we need only show that the principle of optimality applies to the problem.Greedy vs Dynamic 3The 0/1 Knapsack problem•Given a knapsack with weight W > 0. •A set S of n items with weights wi >0 and benefits bi> 0 for i = 1,…,n. •S = { (item1, w1, b1 ), (item2, w2, b2 ) , . . . , ( itemn, wn, bn ) }•Find a subset of the items which does not exceed the weight W of the knapsack and maximizes the benefit.Greedy vs Dynamic 4Determine a subset A of { 1, 2, …, n } that satisfies the following:In 0/1 knapsack a specific item is either selected or notAiiAiiWwb wheremax0/1 Knapsack problemGreedy vs Dynamic 5Variations of the Knapsack problem•Fractions are allowed. This applies to items such as:–bread, for which taking half a loaf makes sense–gold dust•No fractions.–0/1 (1 brown pants, 1 green shirt…)–Allows putting many items of same type in knapsack •5 pairs of socks•10 gold bricks–More than one knapsack, etc.•First 0/1 knapsack problem will be covered then the Fractional knapsack problem.Greedy vs Dynamic 6Brute force!•Generate all 2n subsets•Discard all subsets whose sum of the weights exceed W (not feasible)•Select the maximum total benefit of the remaining (feasible) subsets•What is the run time?O(n 2n), Omega(2n)•Lets try the obvious greedy strategy .Greedy vs Dynamic 7Example with “brute force”S = { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } , W=25•Subsets:1. {}2. { ( item1 , 5, $70 ) } Profit=$703. { (item2 ,10, $90 ) } Profit=$904. { ( item3, 25, $140 ) } Profit=$1405. { ( item1 , 5, $70 ), (item2 ,10, $90 )}. Profit=$160 ****6. { (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W7. { ( item1 , 5, $70 ), ( item3, 25, $140 ) } exceeds W8. { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } exceeds W•Greedy vs Dynamic 8Greedy 1: Selection criteria: Maximum beneficial item. Counter Example: S = { ( item1 , 5, $70 ), (item2 ,10, $90 ), ( item3, 25, $140 ) } 5 lb$7010 lb$90$140W = 25lb25 lbitem1item2item3Knapsack GreedySolution25 lb$140OptimalSolution10 lb5 lb$7010 lb$90=$140=$160Greedy vs Dynamic 9Greedy 2: Selection criteria: Minimum weight itemCounter Example:S = { ( item1 , 5, $150 ), (item2 ,10, $60 ), ( item3, 20, $140 ) } 5 lb$15010 lb$60$140W =30lb20 lbitem1item2item3Knapsack GreedySolution5 lb5 lb20 lb$150$1405 lb10 lb$60$150OptimalSolution=$210=$290Greedy vs Dynamic 10Greedy 3: Selection criteria: Maximum weight item Counter Example:S = { ( item1 , 5, $150 ), (item2 ,10, $60 ), ( item3, 20, $140 ) } 5 lb$15010 lb$60$140W =30lb20 lbitem1item2item3KnapsackGreedySolution5 lb5 lb20 lb$150$14020 lb10 lb$60$140OptimalSolution=$200=$290Greedy vs Dynamic 11Greedy 4: Selection criteria: Maximum benefit per unit item Counter Example S = { ( item1 , 5, $50 ), ( item2, 20, $140 ) (item3 ,10, $60 ), } 5 lb$50W =30lb5 lb5 lb20 lbitem1$14020 lbitem2Knapsack GreedySolution10 lb20 lb$50$140$140$60OptimalSolutionB/W 1: $10B/W 2: $6B/W: $710 lb$60item3=$190=$200What is the asymptotic runtime of this algorithm?Greedy vs Dynamic 12Approximation algorithms•Approximation algorithms attempt to evaluate how far away from the optimum OPT, are the solutions solAlg provided by an algorithm in the worst case•Many criteria are used. We use OPT/solAlg for maximization, and attempt to establish OPT/solAlg<=K where K is a constant (solAlg/OPT for minimization)•The following slides show that the “best” greedy algorithm for 0/1 knapsack, greedy 4 does not satisfy OPT/solAlg<=K •Often greedy4 gives an optimal solutions, but for some problem instances the ratio can become very large•A small modification of greedy4, however, guarantees, that OPT/alg<=2•This is a big improvement.•There are better approximation algorithms for knapsackGreedy vs Dynamic 13Approximation algorithms•Use greedy 4: select the items with maximum benefit per unit.–Implement by Sorting S by benefit per unit.•Example where greedy4 provides a very poor solution:–Assume a 0/1 knapsack problem with n=2–very large W. –S={ ( item1, 1, $2 ), ( item 2, W, $1.5W ) }. •The solution to greedy4 has a benefit of $2•An optimal solution has a benefit of $1.5W.•If we want the best investment and we have W=10,000 dollars. We should