Chapter 16
Greedy algorithms
We consider problems in which a result comprises a sequence of steps or choices that have
to be made to achieve the optimal solution. Greedy programming is a method by which
a solution is determined based on making the locally optimal choice at any given moment.
In other words, we choose the best decision from the viewpoint of the current stage of the
solution.
Depending on the problem, the greedy method of solving a task may or may not be
the best approach. If it is not the best approach, then it often returns a result which is
approximately correct but suboptimal. In such cases dynamic programming or brute-force
can be the optimal approach. On the other hand, if it works correctly, its running time is
usually faster than those of dynamic programming or brute-force.
16.1. The Coin Changing problem
For a given set of denominations, you are asked to find the minimum number of coins with
which a given amount of money can be paid. That problem can be approached by a greedy
algorithm that always selects the largest denomination not exceeding the remaining amount
of money to be paid. As long as the remaining amount is greater than zero, the process is
repeated.
A correct algorithm should always return the minimum number of coins. It turns out
that the greedy algorithm is correct for only some denomination selections, but not for all.
For example, for coins of values 1, 2 and 5 the algorithm returns the optimal number of
coins for each amount of money, but for coins of values 1, 3 and 4 the algorithm may return
a suboptimal result. An amount of 6 will be paid with three coins: 4, 1 and 1 by using the
greedy algorithm. The optimal number of coins is actually only two: 3 and 3.
Consider n denominations 0 < m0 � m1 � . . . � mn−1 and the amount k to be paid.
16.1: The greedy algorithm for finding change.
1 def greedyCoinChanging(M, k):
2 n = len(M)
3 result = []
4 for i in xrange(n - 1, -1, -1):
5 result += [(M[i], k // M[i])]
6 k %= M[i]
7 return result
�c Copyright 2021 by Codility Limited. All Rights Reserved. Unauthorized copying or publication pro-
hibited.
1
The function returns the list of pairs: denomination, number of coins. The time complexity
of the above algorithm is O(n) as the number of coins is added once for every denomination.
16.2. Proving correctness
If we construct an optimal solution by making consecutive choices, then such a property can
be proved by induction: if there exists an optimal solution consistent with the choices that
have been made so far, then there also has to exist an optimal solution consistent with the
next choice (including the situation when the first choice is made).
16.3. Exercise
Problem: There are n > 0 canoeists weighing respectively 1 � w0 � w1 � . . . � wn−1 � 109 .
The goal is to seat them in the minimum number of double canoes whose displacement (the
maximum load) equals k. You may assume that wi � k.
Solution A O(n): The task can be solved by using a greedy algorithm. The heaviest canoeist
is called heavy. Other canoeists who can be seated with heavy in the canoe are called light.
All the other remaining canoeists are also called heavy.
The idea is that, for the heaviest heavy, we should find the heaviest light who can be
seated with him/her. So, we seat together the heaviest heavy and the heaviest light. Let us
note that the lighter the heaviest heavy is, the heavier light can be. Thus, the division between
heavy and light will change over time — as the heaviest heavy gets closer to the pool of light.
16.2: Canoeist in O(n) solution.
1 def greedyCanoeistA(W, k):
2 N = len(W)
3 light = deque()
4 heavy = deque()
5 for i in xrange(N - 1):
6 if W[i] + W[-1] <= k:
7 [Link](W[i])
8 else:
9 [Link](W[i])
10 [Link](W[-1])
11 canoes = 0
12 while (light or heavy):
13 if len(light) > 0:
14 [Link]()
15 [Link]()
16 canoes += 1
17 if (not heavy and light):
18 [Link]([Link]())
19 while (len(heavy) > 1 and heavy[-1] + heavy[0] <= k):
20 [Link]([Link]())
21 return canoes
Proof of correctness: There exists an optimal solution in which the heaviest heavy h and
the heaviest light l are seated together. If there were a better solution in which h sat alone
then l could be seated with him/her anyway. If heavy h were seated with some light x � l,
then x and l could just be swapped. If l has any companion y, x and y would fit together, as
y � h.
The solution for the first canoe is optimal, so the problem can be reduced to seat the
remaining canoeists in the minimum number of canoes.
2
The total time complexity of this solution is O(n). The outer while loop performs O(n) steps
since in each step one or two canoeists are seated in a canoe. The inner while loop in each
step changes a heavy into a light. As at the beginning there are O(n) heavy and with each
step at the outer while loop only one light become a heavy, the overall total number of steps
of the inner while loop has to be O(n).
Solution B O(n): The heaviest canoeist is seated with the lightest, as long as their weight
is less than or equal to k. If not, the heaviest canoeist is seated alone in the canoe.
16.3: Canoeist in O(n) solution.
1 def greedyCanoeistB(W, k):
2 canoes = 0
3 j = 0
4 i = len(W) - 1
5 while (i >= j):
6 if W[i] + W[j] <= k:
7 j += 1;
8 canoes += 1;
9 i -= 1
10 return canoes
The time complexity is O(n), because with each step of the loop, at least one canoeist is
seated.
Proof of correctness: Analogically to solution A. If light l were seated with some heavy
x < h, then x and h could just be swapped.
If the heaviest canoeist is seated alone, it is not possible to seat anybody with him/her.
If there exists a solution in which the heaviest canoeist h is seated with some other x, we can
swap x with the lightest canoeist l, because l can sit in place of x since x � l. Also, x can sit
in place of l, since if l has any companion y, we have y � h.
Every lesson will provide you with programming tasks at [Link]
