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

Question

很抱歉标题有误，所以不允许使用“问题”这个词。我有以下问题：

我有想卖的东西的包装，每个包装都有一个价格。当有人请求X、Y和Z时，我希望查看所有的包，其中一些包包含多个项目，并为用户提供包的组合，这些包将涵盖他们的东西，并具有最低的价格。

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

然而，我还没有找到一篇论文(或任何东西)详细介绍了加权集覆盖问题的最优算法。有人可以帮助实现(我正在使用Python)，一篇论文，甚至是它是如何工作的高级描述吗？

我有成百上千个包，大概有5-6个，所以运行时间并不是问题。

谢谢!

Answer 1

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