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.
Least Change Problem with Thousands of Denominations
c#;algorithms;efficiency
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.