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

Start Free Trial

No credit card required