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

No credit card required

Chapter 4
Dynamic programming
In this chapter, we focus on how to ﬁnd 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 inﬁnite 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 ﬁrst 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.

No credit card required