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