d11wtq wrote:Yeah you want to get the highest multiple each coin makes, then find the "highest common factor" between your desired sum of money, and each type of coin. If you get a HCF, you need that many coins, then recurse down all the coin types collecting the HCFs as you go until you've got no money left.
That's a greedy algorithm for the least amount of coins. But
problem statement wrote:Write a recursive program which numerates all the ways to give the change in coins (quarters, dimes, nickels, pennies) for a given amount of money.
That sounds like backtracking (i suppose you already had greedy and the next topic will be branch-and-bound).
You have a (remaining) amount of money, a set of coins to choose from and something that keeps track of what's been done until now. If your amount is 0 you have a possible way. You can pick each coin with a value less or equal to the remaining amount. Test each coin. If it is it less or equal to the remainig amount pick it and repeat the procedure with [amount minus coin's value].
e.g. the remaining amount is 7. You can't take a quarter: 7-25<0

not feasible. You can't take a dime: 7-10 nf.
(a) You can pick a nickel, remaining amount 2. Or
(b) you can pick a penny, remaining amount 6
Code: Select all
7 - 25 f
7 - 10 nf
7 - 5 -> pick a nickel (a)
2 - 25 nf
2 - 10 nf
2 - 5 nf
2 - 1 -> pick a penny
1 - 25 nf
1 - 10 nf
1 - 5 nf
1 - 1 -> pick a penny
0 -> possible way (n,p,p)
7 - 1 -> pick a penny (b)
6 - 25 nf
6 - 10 nf
6 - 5 -> pick a nickel
1 - 25 nf
1 - 10 nf
1 - 5 nf
1 - 1 -> pick a penny
0 possible way (p,n,p)
6 - 1 -> pick a penny
5 - 25 nf
5 - 10 nf
5 - 5 -> pick a nickel
0 possible way(p,p,n)
5 - 1 -> pick a penny
4 - 25 nf
...
0 possible way(p,p,p,p,p,p,p)
php demonstration
Code: Select all
<?php
function foo($remainingAmount, $sequence) {
/*static */ $coins = array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1);
/* If your amount is 0 you're done. */
if ( 0==$remainingAmount ) {
echo "possible sequence: ", $sequence, "\n";
return;
}
/* You can pick each coin with a value less or equal to the remaining amount.
Test each coin. */
foreach($coins as $coinSymbol=>$coinValue) {
/* If it is it less or equal to the remainig amount */
if ( $remainingAmount>=$coinValue ) {
/* pick it and repeat the procedure (amount minus coin's value) */
foo($remainingAmount-$coinValue, $sequence.$coinSymbol);
}
}
}
foo(7, '', 1);
?>
possible sequence: npp
possible sequence: pnp
possible sequence: ppn
possible sequence: ppppppp
The first three ways are semantically the same - the customer gets two pennies and a nickel.
Possible solution: only allow coins with values equal or less to the current coin for following steps. If you just picked a dime do not try to pick a quarter afterwards but try a dime or a nickel or a penny.
crude php demonstration (that really isn't a good example. sorry)
Code: Select all
<?php
function foo($remainingAmount, $coins, $sequence) {
if ( 0==$remainingAmount ) {
echo "possible sequence: ", $sequence, "\n";
return;
}
reset($coins);
while( list($coinSymbol,$coinValue)=each($coins) ) {
if ( $remainingAmount>=$coinValue ) {
foo($remainingAmount-$coinValue, $coins, $sequence.$coinSymbol);
}
array_shift($coins);
}
}
foo(7, array('q'=>25, 'd'=>10, 'n'=>5, 'p'=>1), '');
?>