# Least Change Problem with Thousands of Denominations

In a hypothetical economy there are currency units that can represent thousands of different values. So, for example there might be coins worth 1c, 3c, 5c, 7c, 7.5c, 80c, 8001.5c etc.

Given a list of all of the possible denominations and an arbitrary value how would one return a list of coins representing the smallest number of coins needed to match that value.

For bonus points, imagine that you have arbitrary finite quantities of each currency. So you may have only two 3c coins but thirty 18c coins.

Sounds like a nightmare compsci class problem but it's something I ran into recently on a personal project of mine.

The economy is a barter economy (tf2) in which every type of item has a distinct value relative to other items. I have an Item class where items have a Value attribute and this attribute is a double that represents the value of the item relative to a base item which has a value of 1. I'm trying to come up with a way so that if someone makes an offer of a value of 30 I can then look through a list of around 1200 item objects and find the smallest set of objects which combine in value to match 30.

I cannot think of a remotely efficient way to do this, but I figured the problem was interesting enough that someone would like to ponder over it with me. My program is in c# but even a psuedocode brainstorm would be helpful.

• The solution is conceptually possible with both of those mechanisms, the issue is that even with 10 or 20 currencies the code takes a non-trivial time to return a solution. Increasing that to 1200 seems unmanageable. – pavja2 Feb 28 '14 at 21:56
• It's not a tractable problem if you require exact precision – Daenyth Feb 28 '14 at 22:00

Sort your objects from highest value to lowest. Find the highest value object that whose value is less than the number you're looking for. If there is no such object, the method fails. If such an object does exist, subtract the object's value from the target number, and use that target number to recursively call the change estimation method. If that call succeeds, you're done. If it fails, try the next lower value object.

• This doesn't always produce the correct solution, as described in the wikipedia page. – Daenyth Feb 28 '14 at 22:04

Mostly you have to do it the hard way in trying every combination, but if you sort the list first, there's a lot of pruning you can do.

First of all, the greedy algorithm on the Change-making problem wikipedia page (choosing the largest denomination not greater than the total amount remaining) is fairly efficient with the right data structures, and will often, but not always, give you the optimal answer. Even when the answer is not optimal, it will usually be close, and is therefore useful as a first step for pruning.

Say the greedy algorithm gives an answer of four items. You now only have to check combinations of three or fewer items.

The other pruning you can do is on the item values. If your total is 30, you know you don't have to test any combinations containing items valued 31 or more. If your first selection has value 20, you know your second selection must have a value less than or equal to 10. Again, this pruning is fairly efficient on a sorted list with the right data structures.

This problem is also a good candidate for memoization, where you store intermediate results rather than recalculating them on every iteration.

Also, the order you perform the search makes a big difference. If you start with the largest items first, you can prune a lot of paths more quickly. No need to cycle through all combinations of \$1 items first.

So while at first glance the problem seems intractable, if you're smart about the order you go in and do some pruning, you should be able to find answers in a reasonable amount of time in practice. At the very worst, you might have to cut off the calculation after a certain time period, but if you order it correctly, you will have a solution that is close to optimal even if you haven't had enough time to prove it is definitely optimal. For the purposes of a game trade, that might be good enough.

I would make this a comment if it weren't so long...because it's not a definitive answer...but anyway:

So, imagining that you need to return 34 cents. You have 1 quarter, 4 dimes, and 3 pennies. You have a problem easily discernible that you have to either give the person 35 cents or 33 cents, but you cannot give exact change.

To code would need to add quarter, check delta (-9). Save as closest delta.

No more quarters, move to dimes. Add dime, check delta (+1). Save as closest delta and pop the dime since we are in a positive delta.

Move to nickels, none. Move to pennies, and add pennies while delta < 0. Final delta when out of pennies (-1). Save as closest delta IF negative delta is given preference over positive delta since the absolute is equal.

Check for lower currency, none.

However, there are other problems...what if you needed to give the user 40 cents...

You have to try quarter + dime + 3 pennies with above algorithm and result in a delta of -2. However, then, you have to roll-back all the way to the quarters and remove one of your top currencies and start over with currencies below that resulting in you finding 4 dimes delta=0, DONE.