这类似于我需要的算法...
我想购买一套完整的交易卡 - 每张卡一张。
每张卡都可以从不同的供应商处以不同的价格购买。如果我从某个供应商处购买给定的卡，他们有时会提供一张或多张附加卡作为 bundle ，但需要额外收费。 bundle 有时可以提供很大的折扣，但一些供应商出售的单件非常便宜，不需要 bundle 。
如果我有每个供应商的每张卡和 bundle 的完整价目表，有人可以建议一种算法来有效计算(或近似)购买整套卡的最便宜方式吗？
最佳答案
首先，我的直觉告诉我，这至少是一个 NP-hard 问题。我认为您无法检查提供的购物车是否实际上是多项式时间内最便宜的。如果您从不同的供应商处购买一张卡并选择完全不同的 bundle ，您可能会丢失卡。您现在可以从不同的供应商处购买那些丢失的卡片以获得新的 bundle ，从而导致一连串的变化。
我将尝试用近似解对已知 NP 问题制定应用。
好的，所以您不仅知道卡片和 bundle 的价格，还知道您需要购买哪些卡片才能激活 bundle 优惠。
听起来您可以在此处采用(修改后的)最小生成树 (MST) 算法。
以下是我认为您应该如何形成有向图:
- 为每张卡片制作一个节点。将这种类型的节点称为
C。 - 为供应商销售的每张卡创建一个额外节点。称这种类型的节点为
CV。 - 将相应的
CV作为源连接到C作为目标。权重为0。 - 对于每个具有捆绑商品的
CV，创建一个节点BCV。使用捆绑价格从CV连接到BCV。 - 从每个
BCV，连接到该束中权重为 0 的所有C。 - 现在创建一个根节点连接到所有
CV类型的节点，每个权重等于该卡的供应商价格。
根据这个公式，您需要一个 MST，它只需要到达 C 类型的节点。此 MST 会告诉您要购买哪些卡以及购买哪些 bundle 。如果您连接到一张卡片 CV，这意味着您已经获得相应的 C(权重为 0，因此它们是免费的)。如果您还选择连接到相应的 BCV，那么您将免费连接到该 bundle 中的所有 C。
事实证明，这些类型的树称为 Steiner 树，并且已知是 NP-hard。 This paper和 this paper我通过谷歌搜索发现的似乎为它提供了一个近似算法。您可以查找更多内容。然而，看起来并没有人真正在某种易于使用的 Python 包中实现了这一点。
关于algorithm - 收集一组项目的优化算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51756865/