CODEWITHSUNDEEP
algorithm
M Krane
M Krane

Reputation: 169

Optimal buying strategy with multiple shops and items

I'm working on a program to "optimally" buy magic cards. On the site each user has a "mini-shop", think eBay without the auctions.

The users enters a list of cards he wants to buy, I then fetch all offers from the site and print an "optimal" shopping list. Optimal meaning cheapest. Prices differ in the shops and also postage changes depending on how many cards you buy.

I would like to implement some algorithm which creates that list for me. I have written one, which works(I think), but I have no idea how good it works.

So my question is this: Can this problem be solved by some existing algorithm? It would need to deal with ~1000 offers for EACH card (normally 40-60 cards, so around 50k different offers)

Can somone point me in the correct direction on this?

Upvotes: 0

Views: 182

Answers (1)

Jon Watte
Jon Watte

Reputation: 7208

The "partition" or "bin packing" problems (which are both mappable to what you want to do) is known to be NP-complete. Thus, the only way to make SURE that you have the optimal solution is to try all possible solutions and pick the best way. If the user wants to buy 1,000 cards, trying all possible options is not computationally feasible, so you need to use heuristics.

Upvotes: 3

Related Questions