On Jan 26, 4:10 pm, Denis Hennessy <de... / hennessynet.com> wrote:
> Here's another test case:
>
> make_change 1000001, [1000000, 1]       # => [1000000, 1]
> AND complete in a  reasonable time (avoid brute force searches)

It should be obvious, but I'll point it out anyway: since make_change
is the knapsack problem (which is NP-complete), it is impossible to
have the solution always be optimal without implementing a brute force
search.  You can prune it somehow, but there will always be a worst
case where you have to search more or less the whole search space.

That said, would you say 5 minutes (3 seconds for 10001, 30 seconds
for 100001, 300 for 1000001) is a reasonable time?

Paolo