ruby - 寻找产品和商店的最佳组合以最小化成本的算法

Question

你好，Stackoverflow 的人们，

我经营一个网站，为用户寻找最便宜的书籍购买地点。这对于单本书来说很容易，但对于多本书来说，有时在一家商店购买一本书而在另一家商店购买另一本书会更便宜。

目前我找到了销售用户列表中所有书籍的最便宜的商店，但我想要一个更智能的系统。这里有更多信息:

• 一本书的价格对于一家商店来说是不变的。
• 运费可能会有所不同，具体取决于书籍的数量或书籍的总值(value)。
• 每个商店对象都可以获取一组书籍并返回运费。
• 通常，并非每家书店都出售每一本书。

不确定在这里链接到我的站点是否很酷，但它列在我的用户配置文件中。

我希望能够找到最便宜的商店和书籍组合。

我担心这需要一种蛮力方法 - 对于 35 家商店，对于数量不多的书籍来说，组合的数量将是巨大的。我感觉组合的数量是 (#shops)^(#books) - 但不是 100%

问题是，我应该使用什么方法？这个问题是否属于众所周知的问题类别？如果需要蛮力，在 Ruby 中执行此操作的好方法是什么？我可以优先考虑商店先尝试吗？

Answer 1

不幸的是，这是一个组合优化问题的示例，没有任何简单的解决方案。你是对的，你实际上确实需要一种蛮力方法。然而!我怀疑这个问题中有一些特殊的结构会有所帮助。例如，当您更改书籍组合时，运费不会随机变化 - 它可能会随着您添加书籍而呈次线性增加和/或饱和。

下面是我的建议:

1. 离线估算每家商店的运输政策，这样，根据给定的书籍(可能还包括它们的重量)，您可以估算运输成本，无需引用他们的网站。
2. 对于每家商店，计算每本书的成本(如果有的话)。
3. 在线下，浏览每家商店或一组商店，并使用您的离线运输政策估算总费用。
4. 选择成本最低的商店。如果有多个相似，则计算出确切答案。

这应该可以帮助您入门，并且不会让您进行全面搜索。