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.