Re: Re: (Golf) Giving Change

[ZZamboni]

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

[no_slogan]

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.