我有我想要购买的物品清单。该项目是由不同的商店和不同的价格提供。商店有个别快递费用。我在寻找一个最佳的购物策略（和一个Java库支持它）与最小的总价格购买所有的项目。

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.

在项目1是提供在Shop1为$ 100个，SHOP2为$ 111 项目2是提供在Shop1为$ 90为SHOP2为$ 85 Shop1的交付成本：$ 10如果订单总额＆LT; $ 150个; $否则为0 SHOP2的交付成本：$ 5如果订单总额＆LT; $ 50; $否则为0 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 如果我买的项目1和项目2在Shop1的总成本为$ 100 + $ 90 + $ 0 = $ 190 如果我买的项目1和项目2在SHOP2的总成本为$ 111 + $ 85±$ 0 = $ 196 如果我买的项目1在Shop1和项目2在SHOP2的总成本为$ 100 + $ 10 + $ 85±$ 0 = 195。 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.

我得到的最低价格，如果我为了项目1和项目2在Shop1：$ 190个

I get the minimal price if I order Item1 and Item2 at Shop1: $190

我需要一些提示该算法可以帮助我解决这类优化问题的大约100和大约20店铺数量的项目数

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.

我已经看了 Apache的数学和它的优化包，但我不知道要查找的算法。

I already looked at apache-math and its optimization package, but I have no idea what algorithm to look for.

Here是一个跟进的问题。

推荐答案

虽然你可以基于Apache单纯求解器实现您的解决方案，你就必须建立在最上层的是大量的code得到它做你想要的。

While you could implement your solution based on the Apache Simplex solver, you'll have to build a lot of code on-top of it to get it to do what you want.

一个更快的方法是使用现成的约束满足包整数域支持优化。有一些开源封装每略有不同的特点。一个吸引我眼球的是霜。这是纯Java实现，具有非常整齐的API，是基于一些算法（分支定界，禁忌，模拟退火，等）。它有一些不错的功能，如使用超时，同时本地搜索等搜索。

A quicker approach is to use a ready-made Constraint Satisfaction package for integer domains which supports optimization. There are a number of open source packages available each with slightly different features. One that caught my eye was Cream. This is implemented purely in Java, has a very neat API, is based on a number of algorithms (branch and bound, taboo, simulated annealing, etc). It has some nice features like searching with time-out, parallel local searches, etc.

有一些其他的包，你可能需要调查，但我不很了解：

There are some other packages which you might want to investigate, but which I don't know much about:

JCL JOPT JCL jOpt