python - 加权集覆盖问题的最优算法？

Question

对标题感到抱歉，SO 不允许在其中使用“问题”一词。我有以下问题:

我有一包我想卖的东西，每个包都有一个价格。当有人请求东西 X、Y 和 Z 时，我想查看所有包，其中一些包含不止一项，并且为用户提供能够满足他们的需求且价格最低的套餐组合。

例如，我可能会建议 [(X, Y), (Z, Q)] 花费 10 美元，因为 [(X), (Y), (Z)] 花费 11 美元。由于这些是价格，我不能使用贪心加权集覆盖算法，因为两个人以不同的价格得到同样的东西是不好的。

但是，我还没有找到一篇论文(或其他任何文章)详细说明加权集覆盖问题的最佳算法。有人可以帮助实现(我使用的是 Python)、论文，甚至是对其工作原理的高级描述吗？

我有数百个包，而且只有 5-6 个，所以运行时间不是真正的问题。

谢谢!

Answer 1

如果您想要一个指数算法，只需尝试包集的每个子集，然后选择包含您需要的所有东西的最便宜的一个。