The Greedy Method 1 The Greedy Method The Greedy Method 1 The Greedy Method The Greedy Method 2 Notes

 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 x