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
In Section
Meditations