Change-making -- in the U.S. at least -- is trivial because the greedy approximation algorithm works perfectly every time. That particular algorithm works perfectly every time because there isn't the kind of overlap in units of money that you would find in, say, a geometric packing problem.
F'rinstance, for any amount of change to be dispensed, you start with quarters. Add quarters until you can't add any more. Next add dimes. Then nickels. Finish it off with pennies.
That can be done in linear time, because it requires no back-tracking, or recursion.
That's true. I guess I was mixing it up with the problem I had in my head, which was: given a particular price, what is the optimal amount to pay so that the number of units – paid plus change – is a minimum.
Which, now that I think of it, might not even be NP. What was the definition again?
That's true. I guess I was mixing it up with the problem I had in my head, which was: given a particular price, what is the optimal amount to pay so that the number of units – paid plus change – is a minimum.
I don't think I understand you here. I did double-check the description of the change-making problem, and it looks like it's only talking about reaching an arbitrary exact sum, with the fewest coins possible, given a set of arbitrary denominations of money. So, you need to give me $US .83 in change, how do you do that using as few coins as possible?
(There's a good, though somewhat technical, paper at http://citeseer.ist.psu.edu/pearson94polynomialtime.html (http://citeseer.ist.psu.edu/pearson94polynomialtime.html).)
The change-making problem can be NP hard in some coin systems. For example, if you had a coin system with a 10-cent coin, a 1-cent coin, and a 6-cent coin, what's the optimal solution for 12 cents? The greedy approximation algorithm would give a dime and two pennies, when what you really want is two 6-cent coins. U.S. money doesn't break down like that though.
Which, now that I think of it, might not even be NP. What was the definition again?
Postde reply to my journal. (http://roaminrob.livejournal.com/50973.html)
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
no subject
Change-making -- in the U.S. at least -- is trivial because the greedy approximation algorithm works perfectly every time. That particular algorithm works perfectly every time because there isn't the kind of overlap in units of money that you would find in, say, a geometric packing problem.
F'rinstance, for any amount of change to be dispensed, you start with quarters. Add quarters until you can't add any more. Next add dimes. Then nickels. Finish it off with pennies.
That can be done in linear time, because it requires no back-tracking, or recursion.
no subject
Which, now that I think of it, might not even be NP. What was the definition again?
no subject
I don't think I understand you here. I did double-check the description of the change-making problem, and it looks like it's only talking about reaching an arbitrary exact sum, with the fewest coins possible, given a set of arbitrary denominations of money. So, you need to give me $US .83 in change, how do you do that using as few coins as possible?
(There's a good, though somewhat technical, paper at http://citeseer.ist.psu.edu/pearson94polynomialtime.html (http://citeseer.ist.psu.edu/pearson94polynomialtime.html).)
The change-making problem can be NP hard in some coin systems. For example, if you had a coin system with a 10-cent coin, a 1-cent coin, and a 6-cent coin, what's the optimal solution for 12 cents? The greedy approximation algorithm would give a dime and two pennies, when what you really want is two 6-cent coins. U.S. money doesn't break down like that though.
Which, now that I think of it, might not even be NP. What was the definition again?
Postde reply to my journal. (http://roaminrob.livejournal.com/50973.html)