Nhân bản – Phụng sự – Khai phóng

Greedy Algorithm
 Greedy algorithms
• The problem of finding the optimal solution
• Divide the problem into many subproblems
• Solve subproblems
• The solutions to the subproblems will be the solution to the given problem
• Divide and conquer algorithm or simple algorithm
• Solve all subproblems
• High complexity (often exponential)
• Easy to design, easy to implement
• Dynamic programming algorithm
• Memorize the solutions of subproblems (when the subproblems are not
completely independent) to avoid duplicate processing
• Lower complexity (usually polynomial functions)
• However, it is difficult to design and implement the solution

2
 Greedy algorithm
• Greedy algorithm principle
• Step-by-step optimization -> global optimization
• Solve only one subproblem
• Do not consider all subproblems
• Build solutions step by step
• At each step, make the best choice at that time (local solution)
– There is no overall solution
• Don't look back and reconsider the decision
• Hope the result is the optimal solution

3
 Greedy algorithm
• Advantage
• easy to design
• easy to implement
• low complexity
• Disadvantages
• Not always the optimal solution
• Difficult to prove the algorithm gives optimal solution

4
 Greedy algorithm
• General structure

greedy(C: set of candidates)

// function returns the optimal solution, including candidates
begin
S =  // S is the solution
while (C   and S is not a solution) do
// choose x from C according to the greedy choice
x = choose(C)
C = C - {x}
if (S U {x} can be a solution) then S := S U {x}
end if
endwhile
if (S is the solution) then return S
else return 0
end if
end
5
 Some applications
• Car rental
• Coin change
• Backpacking
• Find the smallest spanning tree
• Kruskal algorithm
• Prim algorithm
• Find the shortest path
• Dijkstra algorithm

6
 Car rental
• Problem
• There is one car and many customers requesting to rent the car. Each rental request
has a start time and a finish time.
• Problem: how to arrange the requests so that the number of customers who can
rent a car is the largest?

• Formalization
• Suppose C = {a1, a2, …, an} is the set of car rental requests
• For each ai  C, s(ai) is the start time and f(ai) is the finish time
• Let S be the largest set of requirements that satisfy:
• Any two requests must differs in terms of time, meaning that the next request can only
start when the previous request finishes
• Or: a1  S, a2  S: s(a1)  s(a2)  f(a1)  s(a2)

7
 Car rental
• Test 1
• Greedy choice
• Select the request with the shortest rental duration
• Sort car rental requests in ascending order of rental duration
• For example

Optimal solution

1 2
Greedy solution
3

Time

The algorithm does not give optimal solution

8
 Car rental
• Test 2
• Greedy choice
• Select the request with the earliest rental start time
• Sort car rental requests by rental start time
• For example

Optimal solution

2 3 4
Greedy solution

Time

The algorithm does not give the optimal solution

9
 Car rental
• Test 3
• Greedy choice
• Select the request with the earliest rental finish time
• Sort requests in ascending order of rental finish time
• Algorithm gives the optimal solution
• Why?
• Prove!

10
 Car rental

• Prove the algorithm gives the optimal solution

• Suppose S={x1, x2, …, xp} is the solution obtained by the greedy algorithm and G={y1, y2, …, yq}
with qp is an optimal solution.
• We need to prove that S is an optimal solution, meaning that p=q.
• Suppose the elements of sets S and G are arranged in increasing order of rental finish time.
• If G does not contain S, then there must exist k such that: i<k, xi=yi and xkyk.
• Since xk is chosen by the greedy algorithm, xk has the smallest finish time f(xk). So f(xk)f(yk). But
f(yk)s(yk+1), so f(xk)s(yk+1). That is, xk and yk+1 differ in terms of time. In addition, because they
belong to the same solution S, xk-1 and xk differ in terms of time. By the assumption that xk-1 = yk-1,
so yk-1 and xk also differ in terms of time. Replace G by G' = {y1, y2, …, yk-1, xk, yk+1,…, yq} to satisfy
the constraint of time disparity.
• So G' is also an optimal solution that has more requests that coincide with S than with G.
• Repeat the above step, finally get G'' containing S such that |G''|=|G|
• If G'' contains a request that is not in S (i.e. requests that start after xp ends) then that request
would have to be added to S by the greedy algorithm.
• So G’’ = S, but |G''| = |G|, so S is the optimal solution.

11
 Car rental
• Algorithm

rental-car(C)
begin
n = length(C)
// Sort requests by end time in ascending order
C = {a1, a2, …, an } with f(a1)  f(a2)  …  f(an)
S = {a1}
i=1
for j from 2 to n do
if (f(a i )  s(a j )) then
S = S  {a j }
i=j
endif
endfor
return F
end
12
 Car rental
• Algorithm complexity
• Sort the requests
• O(nlogn)
• Building solution
• O(n)

13
 Properties of greedy strategy
• Greedy algorithm
• Determine the solution after a sequence of choices
• At each step, the option that seems best at that step will be selected
• Not always gives optimal solution
• Can any optimization problem be solved by a greedy algorithm?
• Not always true
• However, if a problem has two properties
• The property of greedy choice
• The property of optimal substructure
• Then the problem can be solved by greedy algorithm

14
 Properties of greedy strategy
• Greedy choice property
• There is always an optimal solution that contains a greedy choice
• It should be shown that there exists an optimal solution that always starts with a greedy
choice

• Optimal substructure property

• If S is an optimal solution containing a greedy choice c, then S-{c} is an optimal
solution to a subproblem similar to the original problem that does not contain c
• The optimal solution of a problem must contain the optimal solutions of its subproblems

Proving the optimality of greedy algorithm

15
 Properties of greedy strategy
• If a greedy algorithm satisfies two properties
• Greedy choice property
• Optimal substructure property
• Then the greedy algorithm gives the optimal solution

• Proving
• By the greedy choice property, there exists an optimal solution S containing a greedy choice c 1 .
By the optimal substructure property, S-{c1} is the optimal solution of the subproblem not
containing c1.
• Applied to the subproblem not containing c1, by the greedy choice property, S-{c1} is the
optimal solution containing the greedy choice c2. By the optimal substructure property, S-{c1,
c2} is the optimal solution to the subproblem not containing c1 and c2.
• Continuing to reason like this, we finally have
S-{c1, c2, …, cn} = 
• Or: S = {c1, c2, …, cn}
• So the optimal solution S of the original problem is a sequence of greedy choices made by the
greedy algorithm

16
 Proving optimality of greedy
• 2 ways algorithm
• Directly prove that the algorithm's solution is optimal
• Meaning there is no other better optimal solution

• Prove that the algorithm satisfies two properties

• Greedy choice property
• Optimal substructure property

17
 Money change
• Problem
• Given a monetary system consisting of bills with denominations of 1, 5, 10, 20, 50.
We need to exchange an amount of money S so that the number of bills needed is
the least.
• For example
• 98 = 1 + 1 + 1 + 5 + 50 + 20 + 20

• Brute force algorithm

• List all possible combinations for a total amount of S
• Choose the combination that uses the fewest bills
• Exponential complexity!

18
 Money change
• Greedy algorithm
• Greedy choice
• At each step, choose the highest possible denomination bill without exceeding
the total amount to be exchanged

• Example: S = 98

S =98 S = 48 S = 28 S =8 S =3 S =2 S =1

50 20 20 5 1 1 1

19
 Money change
• Proof (1)
• Suppose F is the optimal solution
• F must satisfy the following constraints
• F can hold up to 4 bills with denomination of 1
– 5 bills with denomination of 1 = 1 bill with denomination of 5
• F can hold at most 1 bill with denomination of 5
– 2 bills of 5 = 1 bill of 10
• F can hold at most 1 bill of 10 denominations.
– 2 bills of 10 = 1 bill of 20
• If F does not contain any bills with denomination of 10, then it can contain at
most 2 bills with denomination of 20
– 3 bills of 20 = 1 bill of 50 + 1 bill of 10
• If F contains a with denomination of 10, then it can contain at most 1 bill with
denomination of 20
– 2 bills of 20 + 1 bill of 10 = 1 bill of 50

20
 Money change
• Proof (2)
• Show that the problem satisfies two properties
• Greedy choice property: it must be shown that there always exists an
optimal solution starting by a greedy choice
• If S  50, the greedy algorithm chooses the bill of 50. It is necessary to prove
that F must start by choosing the bill of 50. By contradiction, suppose F does not
have the bill of 50. Since F must satisfy the above constraints, there can be only
2 possibilities: 4x1+5+10+20 < 50 and 4x1+5+2x20 < 50
So if S  50, F must contain at least one bill of 50
• If 50 > S  20, similarly, F must contain at least one bill of 20
• Continue…

21
 Money change
• Proof (3)
• Optimal substructure property
• Suppose F is the optimal solution for the total amount of money S, p is the bill
finally selected by the greedy algorithm. It should be shown that F-{p} is the
optimal solution to the subproblem S-p.
• Proof by contradiction: Suppose there exists a better optimal solution F' for the
subproblem S-p. Then, F'{p} is an optimal solution better than F for the
problem S. This contradicts the assumption.
So F '{p}= F or F'=F-{p}.

22
 Money change
• Greedy algorithm

money-change(S)
begin
F=
if (S  50 ) then
F = F  {(S div 50) bills of 50}
S = S mod 50
endif
if (S  20 ) then
F = F  {(S div 20) bill of 20}
S = S mod 20
endif
if (S  10 ) then
F = F  {(S div 10) bill of 10}
S = S mod 10
endif
// same for bills of denominations 5, 2, 1
…
end
23
 Money change
• Note
• This greedy algorithm does not give an optimal solution for any monetary system
• For example, the algorithm will not give an optimal solution for the monetary
system {6, 4, 1}
• For instance
–S=8
– Solution given by greedy algorithm: 6 + 1 + 1
– Optimal solution: 4 + 4

24
 Backpacking
• Given n objects and a backpack of maximum weight W
• Each object i has weight wi
• Each object i has value vi
• Let xi be a part of object i, 0  xi  1, xi has weight xiwi and value xivi
• Problem: arrange the objects in the backpack so that the total value of the
backpack is the largest

• This backpacking problem is called “partial” backpacking

• can pack a part of objects into the backpack

• The backpacking problem previously encountered is called the “0-1”

backpack problem
• an object that is either packed in backpack (1) or not packed in backpack (0)

25
 Backpacking
• Idea
• The candidate set is the objects
• At each step, choosing the most promising object and pack as large a portion of it as
possible into the backpack
• For the first selected objects, put all the objects in the backpack
• For the last selected object, it is possible to pack only a part of the object into the
backpack
• The algorithm stops when the backpack is full

• Choose objects by what criteria?

• Descending value
• Ascending weight
• Decreasing value-to-weight ratio (vi/wi)

26
 Backpacking: Example

 Backpack weight is 8 Value Weight Value / Weight

8 2 4
 Descending value
10 5 2
 42 + 36 × 2 / 4 = 60

 Ascending weight 15 3 5

 8 + 15 + 36 × 3 / 4 = 50 36 4 9
 Decreasing value-to-weight ratio
42 6 7
(vi/wi)
 36 + 42 × 4 / 6 = 64

27
 Backpacking
• Greedy choice: Choosing object with decreasing value-to-weight ratio
• Algorithm

backpacking()
begin
Arrange the objects in decreasing order vi/wi
w=W
i=1
while (w  wi) do // put all the objects in the backpack
xi = 1
w = w – wi
i = i +1
endwhile
xi = w/wi // last object selected to be put in the backpack
for k from i + 1 to n do
xi = 0 // objects are not packed in the backpack
endfor
return (x1, x2, …,xn ) // solution
end 28
 Backpacking
• Algorithm
• Complexity analysis
• Sort: O(nlogn)
• Loop: iterating over n objects, so O(n)

29
 Backpacking

• Proving optimality (1)

• Method 1: direct proof (1)
• Suppose v1 /w1  v2/w2  …  vn/wn
• X = {x1, x2, … xn} is the solution determined by the greedy algorithm, V(X) is
the total value
• Suppose j is the smallest index such that xj <1, then X={1,…,1,xj ,0,…,0}
(only the last object is partially selected)
• By contradiction, suppose Y = {y1, y2, … yn} the alternative solution and V(Y)
is the total value
• We have

V ( X )  V (Y )  i 1 xi vi  i 1 yi vi  i 1 vi ( xi  yi )
n n n

vi
 i 1 ( xi  yi ) wi
n

wi
30
 Backpacking

• Proving optimality (2)

• Method 1: direct proof (2)
• There are three cases that can happen:
1. i<j, then xi=1, so xi-yi 0 and vi/wi vj/wj, so
(xi-yi)vi/wi (xi-yi )vj/wj
2. i>j, then xi=0, so xi-yi 0 and vi/wivj/wj , also deduce
(xi-yi)vi/wi (xi-yi)vj/wj
3. i=j, then (xi-yi)vi /wi=(xi-yi)vj/wj
So we have:
vj

vj

n

 i i i w i 1 yi wi  0 do yw
n n
V ( X )  V (Y )  ( x  y ) w  W  W
w j i 1
i i
j i 1

Thus: V(X)  V(Y)

Or V(X) is the optimal solution

31
 Backpacking

• Proving optimality (3)

• Method 2: proving two properties
• Greedy choice property: it is necessary to show that there exists an optimal
solution containing a greedy choice.
– Suppose k is the object with the largest ratio vk/wk , S is an optimal solution, the
value of S is V(S).
– By contradiction, suppose S does not contain k.
– The total value of S is
V ( S )  i 1 xi vi
n

– If some part of the remaining object k is not selected, then, for j  S, xj  0, j  k,

replace j in S by k, with the same weight xjwj = xkwk (so as not to exceed the
backpack weight), we will get a solution S' that is better than S. Contradictory
assumption.

vj vk
x j v j  xk vk chia cho x j w j  xk wk  
wj wk
S must contain object k 32
 Backpacking

• Proving optimality (4)

• Method 2: prove two properties
• Optimal substructure property: if S is an optimal solution containing a
greedy choice c, then there exists an optimal solution S' for the subproblem
not containing c.
– Suppose S is the optimal solution containing object k having the largest ratio
vk/wk with the largest possible weight (p=max(W, wk remaining))
– Then S' =S-{k} is the solution to the subproblem not containing k with the
knapsack of maximum weight decreasing p
– By contradiction, suppose S' is not optimal. Then there exists an S'' that is better
than S' as an optimal solution to a subproblem not containing k. So, S''{k}, for k
of weight p, will be a better solution than S for the original problem. The
assumption contradicts.
– S' must be the optimal solution to the subproblem.

33
 Backpacking

• Note

• The partial backpacking problem is solved by a greedy algorithm

• The 0-1 backpack problem cannot be solved by a greedy algorithm

• In contrast, it is solved by dynamic programming algorithm

34
 Applications in graphs
• Find the smallest spanning tree
• Kruskal algorithm
• Choose the shortest edge
• Prim algorithm
• Choose the shortest edge between vertices in the minimum covering tree and
vertices not in the minimum covering tree

• Find the shortest path

• Dijkstra algorithm
• Choose the shortest edge connecting a visited vertex to an unvisited vertex

35
 Exercises (1)
• Problem 1
• Given set A of n integers, find subset S of A that satisfies:
(i) S has exactly m elements (m  n)
(ii) the sum of the elements of S is the largest
1. Construct a greedy algorithm to determine S
2. Prove the algorithm gives optimal solution

36
 Exercises (2)
• Problem 2
• A barber serves n customers. Each customer requires a different service time .
At any given time, the barber can only serve one customer. The barber needs to
schedule the service of the customers so that the total waiting time and service
time of all customers is minimized.
1. Propose brute force algorithm
2. Build a greedy algorithm
3. Prove the algorithm gives optimal solution
4. Compare complexities of greedy algorithm and brute force algorithm

37
 Exercises (3)

• Problem 3
• There are n jobs, each of which takes 1 unit of time to complete. If each
job i starts before or at time di, it will give the benefit gi.

Build a greedy algorithm to schedule jobs so that the total benefit is maximized
(note that depending on time di, it is not necessary to schedule all the
jobs).

38