java - 如何以最低价格优化购物车？

Question

我有一张我想买的元素 list 。这些元素由不同的商店和不同的价格提供。这些商店有单独的送货费用。我正在寻找以最低总价购买所有商品的最佳购物策略(以及支持它的 Java 库)。

示例:

• 商品 1 在 Shop1 的售价为 100 美元，在 Shop2 的售价为 111 美元。
• 商品 2 在 Shop1 售价 90 美元，在 Shop2 售价 85 美元。
• Shop1 的运费:如果订单总额 < 150 美元，则为 10 美元； $0 否则
• Shop2 的运费:如果订单总额 < 50 美元，则为 5 美元； $0 否则

• 如果我在 Shop1 购买商品 1 和商品 2，总成本为 100 美元 + 90 美元 + 0 美元 = 190 美元。
• 如果我在 Shop2 购买商品 1 和商品 2，总费用为 111 美元 + 85 美元 + 0 美元 = 196 美元。
• 如果我在 Shop1 购买 Item1，在 Shop2 购买 Item2，总成本为 100 美元 + 10 美元 + 85 美元 + 0 美元 =195.

如果我在 Shop1 订购 Item1 和 Item2，我得到的最低价格是:$190

问题

我需要一些提示，哪些算法可以帮助我解决此类商品数量约为 100 家，商店数量约为 20 家的优化问题。

我已经看过 apache-math及其 optimization package , 但我不知道要寻找什么算法。

---

Here是后续问题。

Answer 1

在该包中的所有算法中，没有一个在离散解决方案空间中运行(即没有一个表示您不能在商店 1 购买一半商品，在商店 2 购买一半商品的约束)。

您可能会尝试从良好的初步猜测(例如，不考虑运输成本的最佳解决方案)开始递归地遍历解决方案，并在您当前的解决方案不能比目前所见的最佳解决方案更好时尽早回溯。这是 O(S^I)，但如果商店提供不同的价格，情况可能不会那么糟糕。不过，它会产生最佳解决方案。

您可以尝试一种迭代方法，即从某个解决方案开始，查看相邻的解决方案(不同商店中只有一件商品)，从中选出最好的，然后重复此过程，直到解决方案不再改变。不过，这种方法可能会陷入局部最优，因此它通常是随机的，无论是在起始位置，还是通过以一定概率处理低于最佳邻域的解决方案(参见模拟退火)。

或者如果你真的想深入研究文献，http://en.wikipedia.org/wiki/Combinatorial_optimization是一个很好的起点。