algorithm - 这是NP完全的吗？如果是，背包、MIS、设置填充或调度？

Question

我有一种“直觉”，我在我的应用程序中面临的问题是 NP 完全的，但我正在寻求帮助对其进行分类。

问题

• 我们有一个包含 n 个异构槽的包
• 我们可以在每个插槽中放置一个项目(具有关联值)，或者将其留空。一个插槽最多可以包含一个项目。
• 由于插槽是异构的，插槽 #2 的项目不能放入插槽 #3
• 我们有一组有限的插槽填充操作
• 每个 Action 最多可以调用一次
• 调用给定的 Action 将用固定值(特定于 Action )填充一些(1-n)槽，但前提是所有请求的槽都可用(否则无法调用 Action )，即所有请求的槽或没有。

我们如何确定要调用的操作集以最大化包中的总值(value)？

一个例子:

• 我们有 5 个位置，编号为#1-#5
• 我们有三个 Action ，A1、A2 和 A3
• A1 想把值(value) $30 放在 #1 到 #5 的位置
• A2 想将 50 美元放入插槽 #1 和 #2
• A3 想将 50 美元放入插槽 #4 和 #5

此示例的最佳解决方案是调用操作 A2 和 A3(总值(value)为 200 美元，将插槽 #3 留空)——而不是调用 A1(这将填满所有插槽，但只给出总计 150 美元) .

后续问题 - 我应该如何暴力破解？

一些想法:

• 如果插槽值 ($) 与 A[y] 相关联，我们将要修剪掉与另一个 Action A[x] 覆盖完全相同插槽的任何 Action A[y] ] 小于或等于 A[x]。

• 除此之外，我认为评估解决方案空间归结为迭代所有剩余操作的幂集

• 在所有 Action 的幂集中的集合 {S1, S2...} 中，如果 S2 是 S1 的子集并且所有 Action 都成功应用于 S1，那么我们可以忽略 S2(及其所有子集! ) 而不评估它们，因为它们永远无法给出更好的结果。换句话说，如果我们能在早期找到一个成功应用的集合，我们就可以忽略它的所有子集(显着减少我们必须测试的内容)

有兴趣了解您能想到的任何其他优化。

Answer 1

NP 完全性与决策问题有关，而您的问题是优化问题。如果我们将其更改为可行性(“是否存在 ≥ m 的解决方案？”)，那么我们可以简单地减少 set packing到你的问题，你的问题到 0-1 integer linear programming ，这两者都被认为是 NP 完全的。恭喜，你是 NP 完全的!

我不确定是哪个NPO-complete不过，您的问题属于什么类别。