The Coin Changing Problem The Coin Changing Problem

$
'
The
The Coin
Coin Changing
Changing problem
problem
Suppose we need to make change for 67. We want to do

this using the fewest number of coins possible. Pennies,
nickels, dimes and quarters are available.
Optimal solution for 67 has six coins: two quarters, one
dime, a nickel, and two pennies.
We can use a greedy algorithm to solve this problem:
repeatedly choose the largest coin less than or equal to the
remaining sum, until the desired sum is obtained.
This is how millions of people make change every day (*).
&
CS404/504
Computer Science
Design and Analysis of Algorithms: Lecture 19
'
The
The Coin-Changing
Coin-Changing problem:
problem: formal
formal
description
description
Let D = {d1, d2, ..., dk } be a finite set of distinct coin
denominations. Example: d1 = 25, d2 = 10, d3 = 5, and
d4 = 1.
We can assume each di is an integer and d1 > d2 > ... > dk .
Each denomination is available in unlimited quantity.
The Coin-Changing problem:
Make change for n cents, using a minimum total number
of coins.
Assume that dk = 1 so that there is always a solution.
&
CS404/504
Computer Science
'
The
The Greedy
Greedy Method
Method (works
(works in
in the
the US)
US)
For the coin set { 25, 10, 5, 1}, the greedy method
always finds the optimal solution.
Exercise: prove it.
It may not work for other coin sets. For example it stops
working if we knock out the nickel.
Example: D = { 25, 10, 1} and n = 30. The Greedy
method would produce a solution:
25 + 5 1, which is not as good as 3 10.
&
CS404/504
Computer Science
'
A
A Dynamic
Dynamic Programming
Programming Solution:
Solution: Step
Step (i)
(i)
Step (i): Characterize the structure of a coin-change solution.

Define C[j] to be the minimum number of coins we need to
make change for j cents.
If we knew that an optimal solution for the problem of
making change for j cents used a coin of denomination di ,
we would have:
C[j] = 1 + C[j di].
&
CS404/504
Computer Science
'
A
A Dynamic
Dynamic Programming
Solution: Step
Step (ii)
(ii)
Step (ii): Recursively define the value of an optimal solution.
if j < 0,
if j = 0,
C[j] = 0
1 + min {C[j di]} if j 1

1i<k
&
CS404/504
Computer Science
'
An
An example:
example: coin
coin set
set {{ 50
50,, 25
25,, 10
10,, 1
1}}
C[0] = 0;
C[1] = min
1 + C[1 50] =
C[2] = min
1 + C[1 25] =
1 + C[1 10] =
1 + C[1 1] = 1
1 + C[2 50] =
1 + C[2 25] =
1 + C[2 10] =
1 + C[2 1] = 2
Similarly, C[3] = 3; C[4] = 4; ...; C[9] = 9; C[10] = 1;
&
CS404/504
Computer Science
'
An
An example
example
1 + C[11 50] =
1 + C[11 25] =
C[11] = min
1 + C[11 10] = 2
1 + C[11 1]
=2
{ 1, 10 }
{ 10, 1 }
C[20] = 2; ..., C[29] = 5;
C[30] = min
1 + C[30 50] =
&
CS404/504
1 + C[30 25] = 1 + C[5] = 6

1 + C[30 10] = 1 + C[20] = 3;
1 + C[30 1] = 1 + C[29] = 6;
{ 10, 10, 10 }
Computer Science
'
A
A Dynamic
Dynamic Programming
Solution: Step
Step (iii)
(iii)
Step (iii): Compute values in a bottom-up fashion.
Avoid examining C[j] for j < 0 by ensuring that j di before
looking up C[j di].
COMPUTE-CHANGE(n, d, k)
C[0] := 0
for j := 1 to n do
C[j] :=
for i := 1 to k do
if j di and 1 + C[j di] < C[j] then
C[j] := 1 + C[j di]
return c
Complexity: (nk).
&
CS404/504
Computer Science
'
A
A Dynamic
Dynamic Programming
Solution: Step
Step (iv)
(iv)
Step (iv): Construct an optimal solution.
We use an additional array denom[1..n], where denom[j] is the
denomination of a coin used in an optimal solution to the
problem of making change for j cents.
COMPUTE-CHANGE(n, d, k)
C[0] := 0
for j := 1 to n do
C[j] :=
for i := 1 to k do
if j di and 1 + C[j di] < C[j] then
C[j] := 1 + C[j di]
denom[j] := di
return c
&
CS404/504
Computer Science
'
Step
Step (iv):
(iv): Print
Print optimal
optimal solution
solution
PRINT-COINS(denom, j)
PRINT-COINS(denom, j denom[j])
print denom[j]
Initial call is PRINT-COINS(denom, n).

Example:
&
CS404/504
Computer Science
10
'
Time
Time complexity
complexity of
of DP
DP algorithms
algorithms
Usually the complexity of a DP algorithm is:
# of sub-problems choices for each sub-problem
For example: 0/1 Knapsack Problem:
C[i, ] = max( C[i 1, ], C[i 1, - wi] + pi).
n M sub-problems, each needs to check 2 choices.
(nM )
Matrix Chain Multiplication:
C[i, j] = minik<j {C[i, k] + C[k + 1, j] + rows[Ai ] col[Ak ] col[Aj ]}
n n sub-problems, each needs to check O(n) choices
O(n3)
Coin Changing Problem: size of C = n, k possible coin types
for each C[j]. (nk).
&
CS404/504
Computer Science
11
'
Another
Another Dynamic
Dynamic Programming
Programming Solution
Solution
Let D = {d1, d2, ..., dk } be the set of coin denominations,

arranged such that d1 = 1. As before, the problem is to
make change for n cents using the fewest number of coins.
Use a table C[1..k, 0..n]:
C[i, j] is the smallest number of coins used to make
change for j cents, using only coins d1, d2, ..., di .
The overal number of coins (the final optimal solution)
will be computed in C[k, n].
&
CS404/504
Computer Science
12
'
Another
Another Dynamic
Dynamic Programming
Solution
Step (i): Characterize the structure of a coin-change solution.

Making change for j cents with coins d1, d2, ..., di can be
done in two ways:
1) Dont use coin di (even if its possible):
C[i, j] = C[i 1, j]
2) Use coin di and reduce the amount:
C[i, j] = 1 + C[i, j di ].
We will pick the solution with least number of coins:
C[i, j] = min( C[i 1, j],
&
CS404/504
1 + C[i, j di])
Computer Science
13
'
Another
Another Dynamic
Dynamic Programming
Solution
Step (ii): Recursively define the value of an optimal solution.
if j < 0,
C[i, j] = 0
if j = 0,
min{C[i 1, j], 1 + C[i, j d ]} if j 1

i
&
CS404/504
Computer Science
14
'
Another
Another Dynamic
Dynamic Programming
Solution
Step (iii): Compute values in a bottom-up fashion.
Avoid examining C[i, j] for j < 0 by ensuring that j di before
looking up C[j di]. Overall time complexity is (nk).
COMPUTE-CHANGE(d, k, n)
for i := 1 to k
C[i, 0] := 0
for i := 1 to k
for j := 1 to n
if j < di then
C[i, j] := C[i 1, j]
else
C[i, j] := min(C[i 1, j], 1 + C[i, j di])
&
CS404/504
Computer Science
15
'
Example:
Example: Bottom-up
Bottom-up computation
computation
Suppose we have coin set {d1, d2, d3} = {1c, 4c, 6c} and
n = 8c.
C[i,j] | 0 1 2 3 4 5 6 7 8
----------------------------d1 = 1 | 0 1 2 3 4 5 6 7 8
d2 = 4 | 0 1 2 3 1 2 3 4 2
d3 = 6 | 0 1 2 3 1 2 1 2 2
C[3, 8] = min(C[2, 8], 1 + C[3, 8 d3]) = min(2, 1 + 2)
Evidently, the optimal solution does NOT use d3.
&
CS404/504
Computer Science
16
'
Another
Another Dynamic
Dynamic Programming
Solution
Step (iv): Construct an optimal solution.
Two strategies:
Online: use an additional matrix S[1..k, 0..n], where S[i, j]
indicates which of the values C[i 1, j] and C[i, j di] was
used to compute C[i, j] (use two symbols: and ).
Compute S in parallel with C.
Batch: recover the denominations of the coins used in the
optimal solution by starting backwards from C[k, n], after
computing the entire matrix C.
HW assignment: write the pseudocode for each, analyze time
& space complexity.
&
CS404/504
Computer Science
17

The Coin Changing Problem The Coin Changing Problem

Uploaded by

Copyright:

Available Formats

The Coin Changing Problem The Coin Changing Problem

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

The Coin Changing Problem The Coin Changing Problem

Uploaded by

Copyright:

Available Formats

$

Suppose we need to make change for 67. We want to do

Step (i): Characterize the structure of a coin-change solution.

Step (ii): Recursively define the value of an optimal solution.

1 + min {C[j di]} if j 1

Similarly, C[3] = 3; C[4] = 4; ...; C[9] = 9; C[10] = 1;

C[20] = 2; ..., C[29] = 5;

1 + C[30 25] = 1 + C[5] = 6

Initial call is PRINT-COINS(denom, n).

Let D = {d1, d2, ..., dk } be the set of coin denominations,

Step (i): Characterize the structure of a coin-change solution.

Design and Analysis of Algorithms: Lecture 19

Step (ii): Recursively define the value of an optimal solution.

min{C[i 1, j], 1 + C[i, j d ]} if j 1

You might also like