note
ZZamboni
No, it does not correspond to the <a href="http://hissa.nist.gov/dads/HTML/knapsackProblem.html">0-1 Knapsack problem</a>
(which is NP-complete), but to the
<a href="http://hissa.nist.gov/dads/HTML/fractionalKnapsack.html">fractional
knapsack problem</a>, which can be solved using a greedy algorithm
(put as many of the largest denomination as will fit, then continue
to the next lower denomination, and so on until you reach the
target amount).
<p>--<A HREF="/index.pl?node=ZZamboni&lastnode_id=1072">ZZamboni</A>
87681
87683