Beefy Boxes and Bandwidth Generously Provided by pair Networks vroom
"be consistent"
 
PerlMonks  

Re: Re: (Golf) Giving Change

by ZZamboni (Curate)
on Jun 12, 2001 at 04:23 UTC ( #87690=note: print w/ replies, xml ) Need Help??


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


Comment on Re: Re: (Golf) Giving Change
Re: Re: Re: (Golf) Giving Change
by no_slogan (Chaplain) 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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://87690]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (8)
As of 2014-04-17 09:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (443 votes), past polls