O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 4
Dynamic programming
In this chapter, we focus on how to find optimal dynamic-programming al-
gorithms. Particular attention is paid to problem size in or der to avoid
exponential-cost algorithms. The chapter is illustrated with two classical ex-
amples: the coin changing problem and the knapsack problem. These tech-
niques are then further illustrated with a set of exercises in Section 4.4, with
solutions found in Section 4.5.
4.1 The coin changing problem
The problem is the following: If we want to make change for S cents, an d we
have an infinite supply of each coin in the set Coins = {v
1
, v
2
, . . . , v
n
}, where
v
i
is the value of the i-th coin, what is the minimum number of coins required
to reach the value S?
Greedy algorithm. We propose a greedy algorithm to solve the problem.
First, we sort coins by nonincreasing values, then for each coin value we take
as many coins as possible. The algorithm is formalized as Algorithm 4.1.
1 Sort elements of Coins = {v
1
, . . . , v
n
} by nonincreasing values:
v
1
v
2
··· v
n
2 R S { R is the remaining sum to reach; it is initially S }
3 for i = 1 to n do
4 c
i
=
R
v
i
{ c
i
is the number of coins of value v
i
that are taken }
5 R R c
i
× v
i
{ R is updated }
ALGORITHM 4.1: Greedy algorithm for the coin changing problem.
We first assume that Coins = {10, 5, 2, 1} (a typical European set of coins).
In this case, we can prove that Algorithm 4.1 is optimal:
81
© 2014 by Taylor & Francis Group, LLC

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required