8

你好 Stackoverflow 的人，

我经营一个网站，该网站为其用户寻找最便宜的购买书籍的地方。这对于一本书来说很容易，但对于多本书来说，有时在一家商店购买一本书并从另一家商店购买另一本书可能更便宜。

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

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

不确定在这里链接到我的网站是否很酷，但它列在我的用户资料中。

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

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

问题是，我应该使用什么方法？这个问题是否适合众所周知的一类问题？如果需要蛮力，在 Ruby 中这样做的好方法是什么，我可以优先考虑商店先尝试吗？

4

6 回答 6

6

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

那么我的推荐是这样的：

  1. 离线，估计每家商店的运输政策，这样，给定书籍（可能还有它们的重量），您就可以估算运输成本，而无需参考他们的网站。
  2. 对于每家商店，计算每本书的成本（如果有）。
  3. 离线，浏览每个商店或一组商店，并使用您的离线运输政策估算总成本。
  4. 选择成本最低的商店（或商店）。如果有多个相似的，计算确切的答案。

这应该让你开始，并且会让你没有完整的搜索。

于 2010-01-08T05:13:15.763 回答
2

这是经典上称为“分配问题”的变体。经典的 AP 有一些标准解决方案，包括 Munkres（又名“匈牙利”）算法和 JVC（Junker Volgenant Castanon iirc）算法。

基本思想是计算每个任务的成本（即在每个商店购买每本书的成本），然后选择使总成本最小的任务集。我相信这可以在多项式时间内完成。

每个零售商的运输成本取决于总订单，这一事实使事情变得相当棘手。您可能可以使用一种混合方法，该方法最初不考虑运输成本，然后在您确定了一些有希望的任务后才考虑汇总订单。

祝你好运，听起来是个有趣的问题！

于 2010-01-08T05:15:20.293 回答
2

尝试使用动态编程方法。您可以在此处阅读：http ://www.topcoder.com/tc?module=Static&d1=tutorials&d2= dynProg 您也可以在维基百科或“算法简介”一书（Cormen）中阅读有关它的信息。

这是一个很标准的问题。

于 2010-01-08T05:16:15.300 回答
1

蛮力几乎总是可以被一个好的启发式算法代替，也就是说，一种已知性能不是最优但“足够好”的算法。

虽然我不能 100% 确定，但我想这与背包问题有关（正如我们现在都应该知道的那样，哈哈..）NP 完全问题。

现在没有更好的东西可以提供，但祝你好运！

于 2010-01-08T05:14:14.117 回答
0

这可能是lp问题吗？http://en.wikipedia.org/wiki/Linear_programming

于 2010-01-08T05:34:49.400 回答
0

使用动态编程的无限背包是您的答案。

于 2021-04-11T17:30:27.747 回答