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