Greedy Algorithms
Introduction
Greedy Algorithm
• Greedy algorithms make the choice that looks
best at the moment.
• Find simple and straightforward solutions.
• Gives you locally optimal solution without looking
ahead.
• This locally optimal choice may or may not lead
to a globally optimal solution (i.e. an optimal
solution to the entire problem).
2
Advantages and disadvantages
• Advantages
– Simple
– Quick
– Easy to program
• Disadvantages
– Does not always lead to a global optimal solution.
3
Example
• Find the Shortest Path From a Graph
4
Greedy Algorithms
Part -1 : Greedy Coin Changing Algorithm
Coin Change
6
Objective
Pay out a given sum S with the smallest
number of coins possible.
7
Coin Change
• Assume that we have an unlimited number of coins of
various denominations:
$1, $5, $10, $25, $50
• Now use a greedy method to give the least amount of
coins for $41
41 – 25 = 16 ------ 25
16 – 10 = 6 -------10
6 – 5=1 ------- 5
1 –1=0 -------1
We have to give: 25 10 5 1
8
Making Change – A big problem - 1
• Assume that we have an unlimited number of coins of
various denominations:
$4 , $10, $25
• Now use a greedy method to give the least amount of
coins for $41
41 – 25 = 16 ------ 25
16 – 10 = 6 ------- 10
6– 4 =2 ------- 4
2 ------- ???
We should choose 25 4 4 4 4
9
Making Change – A big problem -2
• Example 2: Coins are valued $30, $20, $5, $1
– 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?)
10
Algorithm
• The greedy coin changing algorithm:
while S > 0 do
c := value of the largest coin no larger than S;
num := S / c;
pay out num coins of value c;
S := S - num*c;
11
Greedy Algorithms
Part -2 : Bin Packing Problem
Concept
13
Bin Packing
• In the bin packing problem, objects of different volumes must be
packed into a finite number of bins or containers each of volume V
in a way that minimizes the number of bins used.
• There are many variations of this problem,
such as 2D packing,
linear packing,
packing by weight,
packing by cost, and so on.
• They have many applications, such as filling up containers, loading
trucks with weight capacity constraints, creating file backups in
media and so on.
14
Ways of Solution
• First Fit Algorithm
• First Fit Decreasing Algorithm
• Full Bin Algorithm
• Other Algorithms
15
Find The Lower Bound
Total size = 12 + 12 + 7 + 6
+ 10 + 4 + 5 + 1 = 57
Bin Size = 20
Lower Bound = 57/20
= 2.85 = 3
16
First Fit Algorithm
• This is a very straightforward greedy
approximation algorithm.
• The algorithm processes the items in arbitrary
order.
• For each item, it attempts to place the item in the
first bin that can accommodate the item. If no bin
is found, it opens a new bin and puts the item
within the new bin.
17
First Fit
18
First Fit Solution
19
First Fit Decreasing Algorithm
• Sort the items in decreasing order.
• Repeat the process First Fit.
20
First Fit Decreasing
21
First Fit Decreasing Solution
22
Full Bin Algorithm
• The full bin packing algorithm is more likely to
produce an optimal solution – using the least
possible number of bins – than the first fit
decreasing and first fit algorithms. It works by
matching object so as to fill as many bins as
possible.
23
Full Bin Concept
• Place the Items into the most full bin, which
could accept it.
• Keeps bins open even when the next item in the
list will not fit in the previous opened bins, in the
hope that a later smaller item will fill.
• Put it in the bins so that smallest empty space is
left.
24
Full Bin Example
25
Full Bin Solution
26
Analysis
• FIRST FIT
– Easiest to use
– Isn’t optimal
• FIRST FIT DCREASING
– Easy to use
– Isn’t optimal always
• FULL BIN
– Optimal
– Difficult to use
27
Try By yourself
28
Greedy Algorithms
Part -3 : Knapsack Problems
Knapsack Problem
• 0/1 Knapsack
– Either take all of an item or none.
• Fractional Knapsack
– You can take fractional amount of an item.
30
Concept of Knapsack Problem
• A Set of Items are given where,
– No of Items = n [X1, X2, X3, ….. Xn]
– Weight of Xi = Wi
– Profit of Xi = Pi
– Knapsack Size = m
• Goal:
– Maximize the Profit ΣPiXi
within ΣWiXi <= m
31
Fractional Knapsack
32
Fractional Knapsack problem
ITEM PRICE WEIGHT Three Cases:
1. Maximum Price
X1 25 18 2. Minimum Weight
3. Maximum Pi/Wi
X2 24 15
X3 15 10 X1 X2 X3 Σ WiXi Σ PiXi
1 2/15 0 20 28.2
Total Item , n = 10
0 10/15 1 20 31
Knapsack Size , m = 20
0 1 1/2 20 31.5
33
0/1 Knapsack
34
Drawbacks of Greedy Methods
Does not always find the optimal solution for
some problems.
35
