How to optimize shopping carts for minimal prices?
- by tangens
I have a list of items I want to buy. The items are offered by different shops and different prices. The shops have individual delivery costs. I'm looking for an optimal shopping strategy (and a java library supporting it) to purchase all of the items with a minimal total price.
Example:
Item1 is offered at Shop1 for $100, at Shop2 for $111.
Item2 is offered at Shop1 for $90, at Shop2 for $85.
Delivery cost of Shop1: $10 if total order < $150; $0 otherwise
Delivery cost of Shop2: $5 if total order < $50; $0 otherwise
If I buy Item1 and Item2 at Shop1 the total cost is $100 + $90 +$0 = $190.
If I buy Item1 and Item2 at Shop2 the total cost is $111 + $85 +$0 = $196.
If I buy Item1 at Shop1 and Item2 at Shop2 the total cost is $100 + $10 + $85 + $0 =
195.
I get the minimal price if I order Item1 at Shop1 and Item2 at Shop2: $195
Question
I need some hints which algorithms may help me to solve optimization problems of this kind for number of items about 100 and number of shops about 20.
I already looked at apache-math and its optimization package, but I have no idea what algorithm to look for.