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.