如何找到一副收藏卡的最佳价格？

Question

或者旅行推销员玩魔术！

我认为这是一个相当有趣的算法挑战。好奇是否有人有任何好的建议来解决它，或者它是否已经可以以已知的方式解决。

TCGPlayer.com< /a> 出售各种游戏的收藏卡，包括万智牌。他们实际上不仅仅是从库存中销售卡片，而是来自多个供应商（50+）的转售商。每个供应商都有不同的卡片库存以及每张卡片不同的价格。每个供应商还收取统一运费（通常）。考虑到所有这些，人们如何找到一副纸牌（例如 40 - 100 张纸牌）的最佳价格？

仅仅找到每张卡的最佳价格是行不通的，因为如果您从 10 个不同的供应商处订购 10 张卡，那么您支付 10 次运费，但如果您从一个供应商处订购所有 10 张卡，您只需支付一次运费。

有一天晚上，我编写了一个简单的 HTML Scraper（使用 HTML Agility Pack）来抓取所有内容每张卡片的不同价格，然后找到携带这副卡片中所有卡片的所有供应商，将每个供应商的卡片价格相加并按价格排序。那真的很容易。总价格最终接近所有卡的总中位价格。

我确实注意到一些单张卡的价格最终远高于中间价格。这就提出了将订单拆分给多个供应商的问题，但前提是通过拆分订单可以节省足够的费用以支付额外的运费（每个添加的供应商都会增加另一笔运费）。

从逻辑上讲，最好的价格可能只涉及几个不同的供应商，但如果卡足够昂贵（有些是)，那么理论上从不同的供应商订购每张卡仍然可以节省足够的费用来证明所有额外的运费是合理的。

如果你要解决这个问题，你会怎么做？纯粹暴力计算卡/供应商组合的每种可能的组合？在我一生中更有可能完成的过程似乎涉及在固定次数的迭代中进行有条理的一系列估计。我有几个想法，但很好奇其他人可能会建议什么。

我更多地寻找算法而不是实际代码。不过，我目前正在使用 .NET，如果这有什么区别的话。

Answer 1

我只是贪婪而已。

假设您要承担运费并向所有供应商购买。计算出您获得的绝对最低价格。然后，针对每个供应商计算出从他们那里购买一些卡与从其他人那里购买卡相比可以节省多少费用。通过运输向供应商订购 - 增量节省。

从提供最少价值的供应商开始，砍掉该供应商，将其卡重新分配给其他供应商，并重新计算增量节省。清洗、漂洗，然后重复，直到最边缘的供应商为您省钱。

这应该能找到一个好的解决方案，但不能保证找到最好的解决方案。然而，找到绝对最佳的解决方案似乎是 NP 困难的。

Answer 2

这与无能力的设施位置问题同构。

• 牌组中的卡：客户

• 供应商：可能的设施位置

• 供应商运费：在某个地点开设设施的成本位置

• 特定供应商的卡成本：从客户到设施的“距离”

设施位置是组合优化文献中经过充分研究的问题。

Answer 3

有趣的问题！ :)

因此，如果我们有 n 张卡和 m 个供应商，那么暴力方法可能必须检查最多 n^m 个组合，对吧（有点少，因为不是每个供应商都有每张卡，但我想这并不重要宏伟的计划；）。

让我们暂时假设每个供应商都有每张卡，然后看看如果没有，情况会如何变化。

1. 找到最便宜的单一供应商解决方案。
2. 按价格订购卡，找到在其他供应商处更便宜的最贵的卡。
3. 对于来自供应商 1 的所有卡，如果供应商 2 更便宜，请将它们移至供应商 2。
4. 如果添加供应商 2 不会使订单更便宜，则撤消并终止，否则从步骤 2 重复。

因此，如果一个供应商没有所有卡，则必须从多供应商情况开始。对于每个供应商，您可以首先购买那里存在的所有卡，然后将算法应用于剩余的卡。

显然，您可能无法使用此方法利用定价中的所有微妙之处。但如果我们假设很大一部分价格差异是由个别高价卡弥补的，我想你可以通过这种方式找到一个合理的解决方案。

---

好吧，写完这一切后我意识到， n^m 假设实际上是错误的。
一旦您选择了一组要购买的供应商，您只需为每张卡选择最便宜的供应商即可。这是一个很大的优势，因为购买每张卡的个人选择不会相互干扰。

这对我们的问题意味着什么？乍一看，这意味着经销商的选择是问题（就计算复杂性而言），而不是您的购买选择的单独分配。因此，在最坏的情况下，您会得到 2^m 种可能的配置，而不是 n^m 种。因此，我们需要的是选择供应商的启发式方法，而不是选择单独的卡。这可能会使上面的启发式实际上更加合理。

Answer 4

我自己也思考过这个问题。考虑以下几点：

如果你需要一周的时间才能弄清楚，
代码、调试和算法
只提供1%的折扣，你愿意吗
做吗？

答案可能是“否”（除非您将一生的积蓄都花在信用卡上，在这种情况下您可能会发疯）。 =)... 或 Amazon.com

因此，已经有一个简单的近似算法：

Wait until you're buying lots of cards (reduce the shipping overhead).
Buy the cards from 3 vendors:
    - the two with the cheapest-but-most-diverse inventories
    - a third which isn't really cheap but definitely has every card you'd want.
Optimize accordingly (for each card, buy from the cheaper one).
Also consider local vendors you could just walk to, pre-constructed decks, and trading.

根据第一手和第二次经验，我可以说您会发现您可以获得中间价格，而您可能会多花几美元的运费，否则，同时仍然接近每个中值。您会发现，您可能需要为库存不足的卡多付一点钱，但这种情况很少见，并且节省的运费将弥补这一点。

我记得古老的编程格言：“永远不要优化，除非绝对必要；很可能你不需要，或者会优化错误的东西。”（例如，你的时间也是一种资源，并且也具有货币价值）

编辑：鉴于此，这是一个非常酷的问题，如果有时间就应该解决它。

Answer 5

我的算法是这样的，

1. 为每张卡计算可用的平均价格，即每个供应商的可用价格总和除以供应商的数量。
2. 现在，为该卡选择一个提供低于或等于平均价格的供应商。
3. 现在，对于每张卡，我们都会有供应商列表。现在，以这种方式走到十字路口，我们最终会看到一系列供应商以平均或低于平均价格提供最大数量的卡。

我仍在考虑下一步，但我把粗略的想法放在这里

• ，现在我们剩下的卡片为我们提供了单张卡片。对于此类卡，我们将查看已入围的供应商的价格表，其中卡数量最多，如果价格差异小于运输成本，我们会将卡添加到该供应商列表中。

我知道这需要巨大的优化。但这是我已经弄清楚的希望这会有所帮助

Answer 6

怎么样：

1. 计算所有供应商每张订购卡的平均价格。
2. 对于至少拥有一张卡的每个供应商，计算订单中所有卡的总节省额，作为该供应商每张卡的价格与平均价格之间的差额。
3. 从总节省最高的供应商开始，然后选择该供应商的所有卡。
4. 继续选择总节省额第二高的供应商，直到您选择了订单中的所有卡片。跳过没有您仍然需要的卡的供应商。
5. 从选定的供应商列表中，将购买的卡重新分配给具有该卡最优惠价格的供应商。
6. 从剩余的供应商列表中，如果列表足够小，您可以对卡数较少的任何供应商进行暴力强制，看看是否可以将卡转移到其他供应商以消除运输成本。

Answer 7

事实上，我去年就写过这篇文章。加载所有价格后我做的第一件事就是清除我的卡池：

• 每个供应商可以有多个
  每张卡的版本，因为有
  重印。找最便宜的。
• 消除任何卡值大于最便宜的卡+运费组合的卡。也就是说，如果我可以一次性向供应商购买该卡，而不是将其添加到您商店的现有订单中，那么我将从其他供应商处购买该卡。
• 消除任何我可以从其他供应商那里购买更便宜的产品（每张卡）的供应商。基本上，如果另一个供应商在每张卡上的价格以及总价格和运费上都比你高，那么你就消失了。

不幸的是，这仍然留下了一个巨大的池子。
然后我进行一些排序、一些强力深度优先求和以及一些修剪，最终得到结果。

不管怎样，我把它调整到可以做 70 张牌，并且在一分钟内达到最佳目标 5% 以内。一个小时内，下降了不到 2%。然后，几天后，实际的最终结果出来了。

我将阅读更多有关设施规划的内容。谢谢你的提示！

Answer 8

如果使用遗传算法呢？我想我自己也尝试一下。您可以通过添加价格最低的染色体和运输成本最低的染色体来操纵池。

顺便说一句，您最终实施了此处提出的解决方案吗？哪一个？为什么？

干杯!