子集和问题的正确定义
Correct definition of The Subset Sum Problem
阅读 Hans Kellerer、Ulrich Pferschy 和 David Pisinger 的书 Knapsack Problems，2004 年版，关于子集和问题，我找到了这个定义（第 4 章）：
Given a set N = {1, ... , n} of n items with positive integer weights
W1, ... , Wn and a capacity c, the subset sum problem (SSP) is to find
a subset of N such that the corresponding total weight is maximized
without exceeding the capacity c.
在第 2.1 节中正式找到（抱歉，不支持 LaTeX）
我在寻找伪代码样本时发现了这个 wikipedia article，其中陈述了一个完全不同但非正式的定义：
given a set (or multiset) of integers, is there a non-empty subset
whose sum is zero?
虽然，它也说这个问题有几个等价的表述，我不相信这个和书上的完全可以称为等价的。
我是不是在看两个不同的问题，认为它们是一样的？我错过了什么？
谢谢
你是对的，这两个定义并不相等。背包问题中的定义描述了一个优化问题。在这种情况下，这是一个 NP-Hard 问题。维基百科上的定义描述了一个存在问题。这是 NP-Complete.
这两个定义的一大区别是正确性的验证。
- 存在性问题很容易在线性时间内得到验证。对解求和，看是否为0。
- 优化的验证很难。计算出的方案真的是最好的，还是有更好的？
阅读 Hans Kellerer、Ulrich Pferschy 和 David Pisinger 的书 Knapsack Problems，2004 年版，关于子集和问题，我找到了这个定义（第 4 章）：
Given a set N = {1, ... , n} of n items with positive integer weights W1, ... , Wn and a capacity c, the subset sum problem (SSP) is to find a subset of N such that the corresponding total weight is maximized without exceeding the capacity c.
在第 2.1 节中正式找到（抱歉，不支持 LaTeX）
我在寻找伪代码样本时发现了这个 wikipedia article，其中陈述了一个完全不同但非正式的定义：
given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?
虽然，它也说这个问题有几个等价的表述，我不相信这个和书上的完全可以称为等价的。
我是不是在看两个不同的问题，认为它们是一样的？我错过了什么？
谢谢
你是对的，这两个定义并不相等。背包问题中的定义描述了一个优化问题。在这种情况下，这是一个 NP-Hard 问题。维基百科上的定义描述了一个存在问题。这是 NP-Complete.
这两个定义的一大区别是正确性的验证。
- 存在性问题很容易在线性时间内得到验证。对解求和，看是否为0。
- 优化的验证很难。计算出的方案真的是最好的，还是有更好的？