<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>5.2 Example: Changing Money</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node25.html#section.scripts.queens"><< Prev</A></TD><TD><A href="node24.html">- Up -</A></TD></TR></TABLE><DIV id="section.scripts.change"><H2><A name="section.scripts.change">5.2 Example: Changing Money</A></H2><DIV class="unnumbered"><H3><A name="label75">Problem Specification</A></H3><P>Given bills and coins of different denominations and an amount <IMG alt="A" src="latex98.png">, select a minimal number of bill and coins to pay <IMG alt="A" src="latex98.png">. One instance of the problem assumes that we want to pay the amount of 1.42, and that we have 6 one dollar bills, 8 quarters (25 cents) , 10 dimes (10 cents), 1 nickel (5 cents), and 5 pennies (1 cent). </P></DIV><DIV class="unnumbered"><H3><A name="label76">Model</A></H3><P>To avoid conversions, we assume that the amount to be paid and all denominations are specified in the same currency unit (e.g., cents). The data is specified by variables <IMG alt="a_1,\ldots,a_k" src="latex123.png"> specifying the available denominations <IMG alt="d_i" src="latex124.png"> and the number <IMG alt="a_i" src="latex125.png"> of available respective coins or bills. </P><P>The model has a variable <IMG alt="C_i" src="latex126.png"> for ever available denomination saying how many of the corresponding bills or coins we will use to pay the amount. For all <I>i</I>, we must have <IMG alt="0\le C_i\le a_i" src="latex127.png"> Moreover, we must satisfy the constraint </P><BLOCKQUOTE><P><IMG alt="d_1\cdot C_1 + d_2\cdot C_2 + \cdots + d_k\cdot
C_k
\;=\;
\mbox{\it amount}" src="latex128.png"></P></BLOCKQUOTE><P> </P></DIV><DIV class="unnumbered"><H3><A name="label77">Distribution Strategy</A></H3><P>We distribute on the variables <IMG alt="C_1,C_2,\ldots" src="latex129.png">, where we give precedence to larger denominations and, with second priority, to larger values. </P><DIV id="progchange"><HR><P><A name="progchange"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">ChangeMoney</SPAN> BillsAndCoins Amount}<BR> Available = {Record<SPAN class="keyword">.</SPAN>map BillsAndCoins <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> A<SPAN class="keyword">#</SPAN>_} A <SPAN class="keyword">end</SPAN>}<BR> Denomination = {Record<SPAN class="keyword">.</SPAN>map BillsAndCoins <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> _<SPAN class="keyword">#</SPAN>D} D <SPAN class="keyword">end</SPAN>}<BR> NbDenoms = {Width Denomination}<BR><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Change}<BR> {FD<SPAN class="keyword">.</SPAN>tuple change NbDenoms 0<SPAN class="keyword">#</SPAN>Amount Change}<BR> {For 1 NbDenoms 1 <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} Change<SPAN class="keyword">.</SPAN>I <SPAN class="keyword">=<:</SPAN> Available<SPAN class="keyword">.</SPAN>I <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>sumC Denomination Change <SPAN class="string">'=:'</SPAN> Amount}<BR> {FD<SPAN class="keyword">.</SPAN>distribute generic(order:naive value:max) Change}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN> <BR> <BR>BillsAndCoins = bac(6<SPAN class="keyword">#</SPAN>100 8<SPAN class="keyword">#</SPAN>25 10<SPAN class="keyword">#</SPAN>10 1<SPAN class="keyword">#</SPAN>5 5<SPAN class="keyword">#</SPAN>1)</CODE></DD></DL><P class="caption"><STRONG>Figure 5.3:</STRONG> A script for changing money together with a data specification.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label78">Script</A></H3><P>The procedure <CODE>ChangeMoney</CODE> in <A href="node26.html#progchange">Figure 5.3</A> takes two parameters specifying the available bills and coins and the amount to be paid. It returns a script that enumerates the possible ways to pay the specified amount with the specified bills and coins. It is assumed that the bills and coins are specified in denomination decreasing order.</P><P>The statement </P><DL class="anonymous"><DD class="code"><CODE>{Browse {SearchOne {ChangeMoney BillsAndCoins 142}}}</CODE></DD></DL><P> computes the list </P><BLOCKQUOTE class="code"><CODE>[change(1 1 1 1 2)]</CODE></BLOCKQUOTE><P> saying that we can pay $1.42 with 1 one dollar bill, 1 quarter, 1 dime, 1 nickel, and 2 pennies. This payment uses the minimal number of bills and coins. The number of different possibilities to pay $1.42 with the specified stock of bills and coins is 6 and can be computed with the statement </P><DL class="anonymous"><DD class="code"><CODE>{Browse {Length {SearchAll {ChangeMoney BillsAndCoins 142}}}}</CODE></DD></DL><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node25.html#section.scripts.queens"><< Prev</A></TD><TD><A href="node24.html">- Up -</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1199
