http://www.perlmonks.org?node_id=87690


in reply to Re: (Golf) Giving Change
in thread (Golf) Giving Change

No, it does not correspond to the 0-1 Knapsack problem (which is NP-complete), but to the fractional knapsack problem, 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).

--ZZamboni

Replies are listed 'Best First'.
Re: Re: Re: (Golf) Giving Change
by no_slogan (Deacon) on Jun 12, 2001 at 04:28 UTC
    Your change is 2.25 10-dollar bills.

    Update: If we could give back part of a bill, we would be talking about the fractional knapsack problem. We can't.