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

Question

9

大家好，Stackoverflow的朋友们，

我运营一个网站，帮助用户找到购买图书最便宜的地方。对于单本书来说很容易，但对于多本书来说，有时从不同的商店购买可能更便宜。

目前我会找到售卖用户清单中所有图书的最便宜商店，但我想要一个更智能的系统。以下是更多信息：

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

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

我担心需要使用蛮力方法——对于35个商店，即使只有少量的书籍，组合数量也将是巨大的。我有一种感觉，组合数是（#商店）^（#书籍）——但不是100％确定。

问题是，我应该采取什么方法？这个问题属于已知类别的问题吗？如果需要蛮力方法，有什么好的Ruby实现方式，我可以优先尝试哪些商店？

- dkam

6个回答

2

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

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

每个零售商的运费取决于总订单的事实使事情变得更加棘手。您可能可以使用混合方法，最初不考虑运费，然后对聚合订单进行考虑，一旦确定了一些有前途的任务。

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

- Drew Hall

2

尝试使用动态规划方法。您可以在此处阅读有关它的内容：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg。您还可以在维基百科或《算法导论》（Cormen）中了解它。这是一个相当标准的问题。

- Hypuk

1

蛮力算法几乎总是可以被一个好的启发式算法所取代，也就是一种已知表现不是最优但足够好的算法。

虽然我不能百分之百确定，但我猜它与背包问题有关，这个问题（我们都应该知道哈哈..）是NP完全的。

暂时没有更好的建议了，祝你好运！

- moritz

0

- Ray Tayek

0

使用动态规划的无界背包问题是您的答案。

- Sunil Garg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter · Accepted Answer

不幸的是，这是一个组合优化问题的例子，没有简单的解决方案。你说得对，一般来说需要采用暴力方法。但是！我怀疑在这个问题中有一些特殊的结构会有所帮助。例如，运输成本不会随着更改书籍的组合而随机变化 - 它可能会随着添加书籍而呈次线性增加和/或饱和。

那么我建议如下：

1.离线估计每家商店的运输政策，以便在没有参考它们的网站的情况下，您可以估算出运输费用（以及可能的重量）。

2.对于每家商店，计算每本书的成本（如果有的话）。

3.离线检查每家商店或商店集，并使用离线运输政策估算总费用。

4.选择费用最便宜的商店（或商店）。如果有多个类似的商店，则计算确切答案。

这应该可以让您入门，并使您避免进行全面搜索。