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)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
timeasmymeasure
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)