algorithm - 约束背包无重量

Question

我刚刚遇到了以下问题(它让我想起了背包问题，但有一些不同):

你有 n 件元素，你必须将这些元素放入你的背包中以获得最大利润。每个项目都有特定的利润值和特定的形状。由于它们的形状，有些元素不能一起放入背包中。与普通的背包问题不同，没有最大重量限制背包中元素的数量。您还将获得每个项目的列表。在该列表中，您可以看到可以放入背包的元素以及相应的元素。

是否有计算最优解的算法？或者它是一个 NP 完全问题？那么，有没有近似的方法呢？

Answer 1

我认为这是NPC。

polynomial verification requirement是微不足道的。

减少到Maximal Independent Set问题。对于每个 MIS 实例 G = (V, E)，构建一组项目 V，每个项目都有单位利润。对于每个项目 v ∈ V，可以放置它的项目列表是它不共享边的顶点集。即，如果 G(v) 是可以与 v 一起使用的项目列表，则 G(v) = {w | (u, w) ∉ E.

如果新问题有一个利润为 k 的解决方案，则它会使用 k 个不在彼此列表中的项目。由此可见，独立集问题存在大小为k的解。