algorithm - 多个商店和元素的最佳购买策略

Question

我正在开发一个“最佳”购买魔法卡的程序。在网站上，每个用户都有一个“迷你商店”，想想没有拍卖的 eBay。

用户输入他想购买的卡片列表，然后我从网站上获取所有优惠并打印“最佳”购物 list 。最优的意思是最便宜的。商店的价格不同，邮费也会根据您购买的卡片数量而变化。

我想实现一些算法来为我创建该列表。我写了一个，它有效(我认为)，但我不知道它的效果如何。

所以我的问题是:这个问题可以用一些现有的算法来解决吗？它需要为每张卡处理大约 1000 个报价(通常是 40-60 张卡，所以大约 50k 个不同的报价)

有人能指出我正确的方向吗？

Answer 1

已知“分区”或“装箱”问题(它们都可以映射到您想要做的事情)是 NP 完全问题。因此，确保您拥有最佳解决方案的唯一方法是尝试所有可能的解决方案并选择最佳方法。如果用户想购买 1,000 张卡片，尝试所有可能的选项在计算上是不可行的，因此您需要使用启发式方法。