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
Read More