       Re: Making Change

• To: mathgroup at smc.vnet.net
• Subject: [mg15178] Re: [mg15160] Making Change
• From: Jurgen Tischer <jtischer at col2.telecom.com.co>
• Date: Fri, 18 Dec 1998 02:10:55 -0500
• References: <199812160811.DAA24583@smc.vnet.net.>
• Sender: owner-wri-mathgroup at wolfram.com

```Wilson,
I've never seen a penny, but that doesn't mean too much since I live in
Colombia. I own a dollar coin, from a trip to Vegas 20 years ago. There
have to be half dollar coins, I cannot imagine Clint Eastwood dropping
a nickel at the bar. So:

In:= coins={100,50,25,10,5,1};

Append[li,#]&/@
Range[0,Quotient[tot-li.Take[coins,Length[li]],
coins[[Length[li]+1]]]])

I won't show you the 293 ways of changing a dollar in all its glory,

In:= allChange

To know the number use Length.

In:= numberChanges0[x_]:=Length[allChange[x]]

In:= numberChanges0

Out= 293

If you are only interested in the number without listing all solutions,
this will do it a bit faster (even with this speedup I hadn't the nerve
to wait for 1000).

In:= numberChanges[x_,1]=1;

In:= numberChanges[x_,n_]:=
Sum[numberChanges[x-k coins[[-n]],n-1],{k,0,Quotient[x,coins[[-n]]]}]

In:= numberChanges[x_]:=numberChanges[x,6]

In:= numberChanges

Out= 293

Jurgen

PS: Don't get a wooden nickel.

Wilson Figueroa wrote:
>
> Hello Group,
>
> I have a question pertaining to making change.
>
> I was reading The Bathroom Trivia Book and came across the following
> statement:
>
>   There are 293 ways to make change for a dollar.
>
> In the book Introduction to Programming with Mathematica by Gaylord,
> Kamin and Wellin there is the following routine:
>
> makeChange[x_]:=Quotient[Drop[FoldList[Mod,x,{25,10,
> 5,1}],-1],{25,10,5,1}]
>
> that will use he fewest of each coin to make change.
>
> is there a way to modify this so that it will enumerate the 293 ways of
> making change for a dollar or any number of bills?
>
> For example, for \$1.00 the output would show
>
> 100, pennies
> 95 pennies, 1 nickel
> 90 pennies, 1 dime
> 90 pennies, 2 nickels
>
> ..
> ..
> ..
>
> and then tell me there are 293 such enumerations.
>
> Thank you for any help.
>
> Wilson
>
> *** Posted from RemarQ - http://www.remarq.com - Discussions Start Here
> (tm) ***

```

• References:
• Prev by Date: Solving with restrictions on parameters
• Next by Date: Re: NIntegrate of a Decaying Exponential
• Previous by thread: Making Change
• Next by thread: Re: Making Change