Help with small program

Tom Plunket tomas at fancy.org
Mon Jan 1 04:27:04 CET 2007


Paul Watson wrote:

> > It is certainly possible to construct a set of denominations for which the
> > algorithm occasionally chooses badly.  For example, if you give it the set
> > (40,35,10) and ask it to make change for 70, it will be suboptimal.
> 
> Unless I am missing the point, the minimum number of coins from the set 
> available will be chosen.  Surely this homework is past due by now.
> 
> [...]
>
> doit(70, (40,35,10))
> 70.0 requires 4 coins in hash  {40: 1, 10: 3}

The point was that "minimum number of coins" in this case is actually
two, but the provided algorithm yields four.

-tom!

-- 



More information about the Python-list mailing list