约束背包无重量
Constrained Knapsack without weight
我刚刚遇到了以下问题（它让我想起了背包问题，但有一些不同）：
你有 n 件物品，你必须将这些物品放入你的背包中以获得最大利润。每个项目都有特定的利润值和特定的形状。由于它们的形状，有些物品不能一起放入背包中。与普通的背包问题不同，没有最大重量限制背包中物品的数量。
您还将获得每个项目的列表。在该列表中您可以看到可以放入背包的物品以及相应的物品。
有计算最优解的算法吗？
或者它是一个 NP 完全问题？那么，有没有近似的方法呢？
我认为这是NPC
polynomial verification requirement 是微不足道的。
还原是针对Maximal Independent Set的问题。对于每个 MIS 实例 G = (V, E)，构造一组项目 V，每个项目都有单位利润。对于每个项目 v ∈ V，它可以放置的项目列表是它不共享边的顶点集。即，如果 G(v) 是可以与 v 一起使用的项目列表，则 G(v) = {瓦 | (u, w) ∉ E}.
如果新问题有一个利润为 k 的解决方案，则它使用 k 个不在彼此列表中的项目.由此可见独立集问题有大小k的解
我刚刚遇到了以下问题（它让我想起了背包问题，但有一些不同）：
你有 n 件物品，你必须将这些物品放入你的背包中以获得最大利润。每个项目都有特定的利润值和特定的形状。由于它们的形状，有些物品不能一起放入背包中。与普通的背包问题不同，没有最大重量限制背包中物品的数量。 您还将获得每个项目的列表。在该列表中您可以看到可以放入背包的物品以及相应的物品。
有计算最优解的算法吗？ 或者它是一个 NP 完全问题？那么，有没有近似的方法呢？
我认为这是NPC
polynomial verification requirement 是微不足道的。
还原是针对Maximal Independent Set的问题。对于每个 MIS 实例 G = (V, E)，构造一组项目 V，每个项目都有单位利润。对于每个项目 v ∈ V，它可以放置的项目列表是它不共享边的顶点集。即，如果 G(v) 是可以与 v 一起使用的项目列表，则 G(v) = {瓦 | (u, w) ∉ E}.
如果新问题有一个利润为 k 的解决方案，则它使用 k 个不在彼此列表中的项目.由此可见独立集问题有大小k的解