Courses

# The Greedy Method 1 The Greedy Method The Greedy Method 1 The Greedy Method The Greedy Method 2 Notes | EduRev

## : The Greedy Method 1 The Greedy Method The Greedy Method 1 The Greedy Method The Greedy Method 2 Notes | EduRev

``` Page 1

The Greedy Method 1
The Greedy Method
Page 2

The Greedy Method 1
The Greedy Method
The Greedy Method 2
The Greedy Method Technique (§5.1)
Fractional Knapsack Problem (§5.1.1)
Minimum Spanning Trees (§7.3) [future lecture]
Page 3

The Greedy Method 1
The Greedy Method
The Greedy Method 2
The Greedy Method Technique (§5.1)
Fractional Knapsack Problem (§5.1.1)
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
The Greedy Method Technique (§5.1)
Fractional Knapsack Problem (§5.1.1)
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
The Greedy Method Technique (§5.1)
Fractional Knapsack Problem (§5.1.1)
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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!