具有多个目标的子集总和的复杂性
Complexity of subset sum with multiple targets
下面的问题是NP-Complete还是P？
输入：一组正整数{a1,a2,...,an)和一个正整数M
问题：是否存在S的子集S'，使得S'中的所有元素之和为M-1、M或M+1。
我的猜测是它在 NP-Complete 中并且与子集总和相关。但是我很难减少这个问题的子集总和。
这是 NP 完全的。给定子集 sum
的实例
Find a subset of {x1, ... xn} with sum X
考虑以下问题实例
Find a subset of {4 * x1, 4 * x2, ..., 4 * xn} with sum 4*X, 4*X-1 or 4*X + 1
通过考虑被 4 整除，很明显任何总和为 4*X、4*X-1 或 4*X + 1 的子集实际上必须总和为 4X。但这随后通过除以 4 平凡地给出了原始子集和问题的解决方案。
下面的问题是NP-Complete还是P？
输入：一组正整数{a1,a2,...,an)和一个正整数M
问题：是否存在S的子集S'，使得S'中的所有元素之和为M-1、M或M+1。
我的猜测是它在 NP-Complete 中并且与子集总和相关。但是我很难减少这个问题的子集总和。
这是 NP 完全的。给定子集 sum
的实例Find a subset of {x1, ... xn} with sum X
考虑以下问题实例
Find a subset of {4 * x1, 4 * x2, ..., 4 * xn} with sum 4*X, 4*X-1 or 4*X + 1
通过考虑被 4 整除，很明显任何总和为 4*X、4*X-1 或 4*X + 1 的子集实际上必须总和为 4X。但这随后通过除以 4 平凡地给出了原始子集和问题的解决方案。