这是NP完全的吗？如果是，背包、MIS、设置填充或调度？
Is this NP-Complete? If so, knapsack, MIS, set-filling or scheduling?
我 "gut-feeling" 我在我的应用程序中遇到的问题是 NP 完全问题，但我正在寻求帮助对其进行分类。
问题
- 我们有一个包有 n 个 异构 个插槽
- 我们可以在每个插槽中放置一个项目（具有关联值），或者将其留空。一个插槽最多可以包含一个项目。
- 由于槽位不同，槽位 #2 的项目不能进入槽位 #3
- 我们有一组有限的插槽填充操作
- 每个动作最多可以调用一次
- 调用给定的动作将用固定值（特定于动作）填充一些（1-n）槽，但前提是所有请求的槽都可用（否则无法调用动作），即所有请求插槽或 none.
我们如何确定要调用的操作集以最大化包中的总价值？
一个例子：
- 我们有 5 个插槽，编号为 #1-#5
- 我们有三个动作，A1、A2 和 A3
- A1 想要将价值 $30 放入插槽 #1 到 #5
- A2 想将 50 美元放入插槽 #1 和 #2
- A3 想将 50 美元放入插槽 #4 和 #5
此示例的最佳解决方案是调用操作 A2 和 A3（总价值为 200 美元，将插槽 #3 留空）- 而不是调用 A1（这将填充所有插槽，但只给出总共150 美元）。
后续问题 - 我该如何暴力破解？
一些想法：
如果插槽值 ( $) 与 A[y] 相关联小于或等于 A[x].
除此之外，我认为评估解决方案 space 归结为遍历所有剩余动作的幂集
在所有动作的幂集中的集合 {S1, S2...} 中，如果 S2 是 S1 的子集并且所有动作都成功应用于 S1 那么我们可以忽略 S2（并且所有它的子集！）而不评估它们，因为它们永远不会给出更好的结果。换句话说，如果我们能在早期找到一个成功应用的集合，我们就可以忽略它的所有子集（显着减少我们必须测试的内容）
有兴趣了解您能想到的任何其他优化。
NP完备性是决策问题，你的是优化问题。如果我们将其更改为可行性 ("does a solution ≥ m exist?")，那么我们可以简单地减少 set packing to your problem, and your problem to 0-1 integer linear programming，这两者都被认为是 NP 完全的。恭喜你，你是 NP 完全的！
我不确定你的问题属于哪个 NPO-complete class。
我 "gut-feeling" 我在我的应用程序中遇到的问题是 NP 完全问题，但我正在寻求帮助对其进行分类。
问题
- 我们有一个包有 n 个 异构 个插槽
- 我们可以在每个插槽中放置一个项目（具有关联值），或者将其留空。一个插槽最多可以包含一个项目。
- 由于槽位不同，槽位 #2 的项目不能进入槽位 #3
- 我们有一组有限的插槽填充操作
- 每个动作最多可以调用一次
- 调用给定的动作将用固定值（特定于动作）填充一些（1-n）槽，但前提是所有请求的槽都可用（否则无法调用动作），即所有请求插槽或 none.
我们如何确定要调用的操作集以最大化包中的总价值？
一个例子：
- 我们有 5 个插槽，编号为 #1-#5
- 我们有三个动作，A1、A2 和 A3
- A1 想要将价值 $30 放入插槽 #1 到 #5
- A2 想将 50 美元放入插槽 #1 和 #2
- A3 想将 50 美元放入插槽 #4 和 #5
此示例的最佳解决方案是调用操作 A2 和 A3（总价值为 200 美元，将插槽 #3 留空）- 而不是调用 A1（这将填充所有插槽，但只给出总共150 美元）。
后续问题 - 我该如何暴力破解？
一些想法：
如果插槽值 ( $) 与 A[y] 相关联小于或等于 A[x].
除此之外，我认为评估解决方案 space 归结为遍历所有剩余动作的幂集
在所有动作的幂集中的集合 {S1, S2...} 中，如果 S2 是 S1 的子集并且所有动作都成功应用于 S1 那么我们可以忽略 S2（并且所有它的子集！）而不评估它们，因为它们永远不会给出更好的结果。换句话说，如果我们能在早期找到一个成功应用的集合，我们就可以忽略它的所有子集（显着减少我们必须测试的内容）
有兴趣了解您能想到的任何其他优化。
NP完备性是决策问题，你的是优化问题。如果我们将其更改为可行性 ("does a solution ≥ m exist?")，那么我们可以简单地减少 set packing to your problem, and your problem to 0-1 integer linear programming，这两者都被认为是 NP 完全的。恭喜你，你是 NP 完全的！
我不确定你的问题属于哪个 NPO-complete class。