Page 1 The Greedy Method 1 The Greedy Method Page 2 The Greedy Method 1 The Greedy Method The Greedy Method 2 Outline and Reading The Greedy Method Technique (§5.1) Fractional Knapsack Problem (§5.1.1) Task Scheduling (§5.1.2) Minimum Spanning Trees (§7.3) [future lecture] Page 3 The Greedy Method 1 The Greedy Method The Greedy Method 2 Outline and Reading The Greedy Method Technique (§5.1) Fractional Knapsack Problem (§5.1.1) Task Scheduling (§5.1.2) Minimum Spanning Trees (§7.3) [future lecture] The Greedy Method 3 The Greedy Method Technique The greedy method is a general algorithm design paradigm, built on the following elements: ? configurations: different choices, collections, or values to find ? objective function: a score assigned to configurations, which we want to either maximize or minimize It works best when applied to problems with the greedy-choice property: ? a globally-optimal solution can always be found by a series of local improvements from a starting configuration. Page 4 The Greedy Method 1 The Greedy Method The Greedy Method 2 Outline and Reading The Greedy Method Technique (§5.1) Fractional Knapsack Problem (§5.1.1) Task Scheduling (§5.1.2) Minimum Spanning Trees (§7.3) [future lecture] The Greedy Method 3 The Greedy Method Technique The greedy method is a general algorithm design paradigm, built on the following elements: ? configurations: different choices, collections, or values to find ? objective function: a score assigned to configurations, which we want to either maximize or minimize It works best when applied to problems with the greedy-choice property: ? a globally-optimal solution can always be found by a series of local improvements from a starting configuration. The Greedy Method 4 Making Change Problem: Accept n dollars, to return a collection of coins with a total value of n dollars. Configuration: A collection of coins with a total value of n Objective function: Minimize number of coins returned. Greedy solution: Always return the largest coin you can Example 1: Coins are valued $.32, $.08, $.01 ? Has the greedy-choice property, since no amount over $.32 can be made with a minimum number of coins by omitting a $.32 coin (similarly for amounts over $.08, but under $.32). ? For a certain amount (y) over a coin dimension (x), if we can reach it using coins (<x) with a total n coins, then we can also use coin x with = n coins. Example 2: Coins are valued $.30, $.20, $.05, $.01 ? Does not have greedy-choice property, since $.40 is best made with two $.20’s, but the greedy solution will pick three coins (which ones?) Page 5 The Greedy Method 1 The Greedy Method The Greedy Method 2 Outline and Reading The Greedy Method Technique (§5.1) Fractional Knapsack Problem (§5.1.1) Task Scheduling (§5.1.2) Minimum Spanning Trees (§7.3) [future lecture] The Greedy Method 3 The Greedy Method Technique The greedy method is a general algorithm design paradigm, built on the following elements: ? configurations: different choices, collections, or values to find ? objective function: a score assigned to configurations, which we want to either maximize or minimize It works best when applied to problems with the greedy-choice property: ? a globally-optimal solution can always be found by a series of local improvements from a starting configuration. The Greedy Method 4 Making Change Problem: Accept n dollars, to return a collection of coins with a total value of n dollars. Configuration: A collection of coins with a total value of n Objective function: Minimize number of coins returned. Greedy solution: Always return the largest coin you can Example 1: Coins are valued $.32, $.08, $.01 ? Has the greedy-choice property, since no amount over $.32 can be made with a minimum number of coins by omitting a $.32 coin (similarly for amounts over $.08, but under $.32). ? For a certain amount (y) over a coin dimension (x), if we can reach it using coins (<x) with a total n coins, then we can also use coin x with = n coins. Example 2: Coins are valued $.30, $.20, $.05, $.01 ? Does not have greedy-choice property, since $.40 is best made with two $.20’s, but the greedy solution will pick three coins (which ones?) The Greedy Method 5 The Fractional Knapsack Problem Given: A set S of n items, with each item i having ? b i - a positive benefit ? w i - a positive weight Goal: Choose items with maximum total benefit but with weight at most W. If we are allowed to take fractional amounts, then this is the fractional knapsack problem. ? In this case, we let x i denote the amount we take of item i ? Objective: maximize ? Constraint: ? ?S i i i i w x b ) / ( ? ? = S i i W xRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!