确定最便宜的方式在线购买n种产品

Question

我目前正在研究一个简单的个人用脚本，它将列出我想要购买的所有物品以及价格比较器中每件物品的价格，并尝试找到最便宜的方式来购买所有这些商品（请记住，如果您从同一商店购买多件商品，则只需支付一次运费）。最简单的方法是什么？

我想过用匈牙利算法对于这一点，但意识到这可能不是来自同一家商店买最好的想法往往正是我们做想，不是回避。另一方面，试图贪婪地发现手头物品最多的商店也不足以导致他们出售这些商品并不意味着他们以最优惠的价格出售它们，即使我们只支付一次运输费用。

你会推荐什么？有一些容易实现的解决方案吗？

Answer 1

这不是一个答案，而是对你的问题的澄清。由于评论太长，我在这里发布。

让有M店铺和N项目。给出矩阵A，其中A(i, j)是从商店i购买商品j的价格（如果商店i不销售商品j，则我们将A(i, j)设置为无穷大）。还给出了一个数组S，其中S(i)是店铺i的运输成本。

问题：找到函数b:{1,...,N} -> {1,...,M}，这意味着从商店b(j)，最大限度地减少总成本购买项目j。

您已经可以看到这与匈牙利算法的设置不同，后者要求最小化PERMUTATION的排列顺序为{1,...,N}。

在这一点上，有关于输入的性质几个问题：

• 什么是M和N范围？如果其中任何一个非常小（例如< 20），则指数算法可能是可接受的。
• 是矩阵A稀疏（即大多数商品只能在少数商店购买）或密集（即大多数商品在大多数商店中都可用）？

Answer 2

我觉得这是一个很难解决的问题就是这样，因为如果你能解决这个问题正是你可能需要从https://en.wikipedia.org/wiki/Set_cover_problem问题，并建立了成本，使确切的解决您的问题将集合覆盖问题的解决方案。可能在该文章或其他地方给出的一些近似解决方案会有所帮助。将高科技引入它的最简单方法可能是找到一个整数线性编程包并使用它。