如何找到一张收藏卡的最优惠价格？

Question

或者旅行推销员扮演魔术!

我认为这是一个相当有趣的算法挑战.好奇,如果有人有任何好的解决方案的建议,或者它已经以已知的方式解决.

TCGPlayer.com为各种游戏销售收藏卡,包括Magic the Gathering.它们实际上是来自多个供应商(50+)的转售商,而不仅仅是从他们的库存中销售卡片.每个供应商都有不同的卡片库存和每张卡的不同价格.每个供应商也收取统一运费(通常).鉴于所有这些,如何找到一副牌的最佳价格(比如说40到100张牌)？

只是找到每张卡的最优价格是行不通的,因为如果您从10个不同的供应商订购10张卡,那么您支付10次运费,但如果您从一个供应商订购所有10个卡,则只支付一次运费.

另一天晚上,我写了一个简单的HTML Scraper(使用HTML Agility Pack),它可以获取每张卡的所有不同价格,然后找到所有带有卡中所有卡的供应商,总计来自每个供应商的卡的价格和按价格排序.这真的很容易.总价格最终接近所有卡的总中位数价格.

我注意到一些个人卡最终远高于中位数价格.这引发了在多个供应商之间拆分订单的问题,但只有通过将订单拆分以支付额外运费(每个添加的供应商增加另一个运费)才能节省足够的成本.

从逻辑上看,似乎最好的价格可能只涉及一些不同的供应商,但如果这些卡足够昂贵(有些是),那么理论上从不同的供应商订购每张卡仍然可以节省足够的成本以证明所有额外的运费.

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

我正在寻找比实际代码更多的算法.我目前正在使用.NET,如果这有任何区别.

Answer 1

我会贪婪的.

假设您要吃掉运费并从所有供应商那里购买.计算出你得到的绝对最低价格.然后,对于每个供应商计算出能够从他们那里购买一些卡而不是其他人拯救你.通过运输订购供应商 - 增量节省.

从提供最低价值的供应商开始,瞄准该供应商,将其卡重新分发给其他供应商,并重新计算增量节省.洗涤,冲洗并重复,直到最边缘的供应商为您省钱.

这应该找到一个很好的解决方案,但不能保证找到最佳解决方案.然而,找到绝对最佳的解决方案似乎很难实现NP.