Author |
Topic: coin denomination (Read 1262 times) |
|
hary
Junior Member
Posts: 107
|
 |
coin denomination
« on: Feb 2nd, 2010, 11:28am » |
 Quote  Modify
|
You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible. [on problem set 4]
Its a famous problem and is also listed on one of the links, pasted against the solution to one of problems i raised.
I am stuck in understanding solution to this problem
e.g. if i have denomination values
2, 3, 7, 8 and i want to make a change for 17. How would this get solved. ( i need help since i am sure i am not discerning the solution correctly)
|
|
 IP Logged |
|
|
|
mmgc
Newbie
Gender: 
Posts: 47
|
|
Re: coin denomination
« Reply #1 on: Feb 2nd, 2010, 8:52pm » |
Quote Modify
|
Start with sum ( amount ) = 0, for S( 0 ) , 0 coins are required. S ( 1 ) is not possible. S ( 2 ) = 2 + S ( 0 ) = total 1 coin is required. S ( 3 ) = 2 + S ( 1 ) (not possible) or 3 + S ( 0 ) = 1 coin is needed, S ( 4 ) = 2 + S ( 2 ) or 3 + S ( 1 ) = 2 coins, S ( 5 ) = 2 + S ( 3 ) or 3 + S ( 2 ) = again 2 coins, S ( 6 ) = 2 + S ( 4 ) or 3 + S ( 3 ) = 2 coins (minimum) ,S ( 7 ) = 2 + S ( 5 ) or 3 + S ( 4 ) or 7 = 1 coin and so on….
Amount Number of Coins Sum which leads to this sum
0 0 -
1 n/a n/a
2 1 0
3 1 0
4 2 2
5 2 2
6 2 3
7 1 0
8 3 6
9 2 7
10 2 7
11 2 3
12 3 10
13 3 11
14 2 7
15 2 7
16 3 14
17 3 15
Note: We can get the sum with the combination of other coins also ( probably with the same number of coins)
|
|
IP Logged |
|
|
|
hary
Junior Member
Posts: 107
|
|
Re: coin denomination
« Reply #2 on: Feb 2nd, 2010, 10:11pm » |
Quote Modify
|
Thanks mmgc its pretty clear with your explaination 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print