Name: The Masked Poopy 2012-05-07 18:13
Alright /prog/, I'm coming here for help with an algorithm I've been trying to solve but I think the problem may be intractable.
Essentially, I have n unique thing I want to buy in a market with m sellers. Not all of the m sellers sell each items. I want to construct a set of purchases so that I buy all n items the cheapest way possible. This problem, in its current form, is quite easy and can be solved by greedily buying from the cheapest offer for each item.
Here is the hard part: for these items, transactions can only be made in whole units, however items are priced to 3 decimals. Therefor if I buy something for 1.550, I end up paying 2 for it. If I buy 2 items for 1.550 and 1.300 from a seller however, I end up paying only 3 for them. How can I compute the most efficient way to buy all the items? Keep in mind my input size may be up to 200 items and 20 (possibly) unique sellers per item?
Essentially, I have n unique thing I want to buy in a market with m sellers. Not all of the m sellers sell each items. I want to construct a set of purchases so that I buy all n items the cheapest way possible. This problem, in its current form, is quite easy and can be solved by greedily buying from the cheapest offer for each item.
Here is the hard part: for these items, transactions can only be made in whole units, however items are priced to 3 decimals. Therefor if I buy something for 1.550, I end up paying 2 for it. If I buy 2 items for 1.550 and 1.300 from a seller however, I end up paying only 3 for them. How can I compute the most efficient way to buy all the items? Keep in mind my input size may be up to 200 items and 20 (possibly) unique sellers per item?