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

Question

你好Stackoverflow人,

我经营一个网站,发现其用户是最便宜的购买书籍的地方.这对于一本书来说很容易,但对于多本书来说,在一家商店购买一本书和从另一家商店购买另一本书有时会更便宜.

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

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

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

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

我担心它需要蛮力的方法 - 并且有35家商店,对于适量的书籍来说,组合的数量将是巨大的.我觉得组合的数量是(#shops)^(#books) - 但不是100%

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

Answer 1

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

这是我推荐的,然后:

1. 离线,估计每个商店的运输政策,这样,给定书籍(可能还有他们的重量),您可以估算运费而不参考他们的网站.
2. 对于每个商店,计算每本书的成本(如果有的话).
3. 离线,浏览每个商店或一组商店,并使用您的离线运送政策估算总费用.
4. 选择最便宜的商店(或商店).如果有多个相似,请计算确切的答案.

这应该让你开始,并将让你没有完整的搜索.