给出 \(\{a_{1\dots n}\}\)，找出一个子集和为 \(0\)。
这是 NPC 的，当 \(|a_i| \leq n\) 的时候可以 \(n^3\) 背包，当然地可以使用 bitset 压位至 \(\frac {n^3} w\)。
值域还是太难受了，考虑怎么压下来值域，因为和为 \(0\)，值域又是 \(n\)，通过调整顺序总是存在一种方案使得值域在 \([-n,n]\)。但是我们不知道这个顺序，但感觉存太大值域又没用。
所以随机一个顺序，可以证明这个时候值域期望是不大于 \(O(n^{1.5})\) 的，复杂度可以做到 \(O(\frac {n^{2.5}} w)\)。
还能再给力一点吗？
时间复杂度 \(O(nA)\)，空间线性的 01 背包可行性及方案构造(Pisinger, 1999)
因为在很多情况下值域开大到 \(nA\) 是很浪费的，中途偏差其实和 \(s\) 差距不会太大——也总是存在一种顺序使得中途偏差不超过 \(A\)，前面考虑找到这样的顺序，但是发现不太现实，所以现在来考虑另一种：边加边删。
我们先随便找到一个和与 \(s\) 差不超过 \(A\) 的集合，然后接下来 加入其它数或者删除已经加入的数，那么这样我们考虑的值域就是 \(O(A)\) 的了。
但是删除确实是一件很困难的事情，并不是所有数都能删，我们不能删除之前没加进来的数，我们也不能记录目前集合。
但是如果只在 dp 里面放一个可行性，那属实是有点浪费我们这么小的值域，而且如果要把可删除的信息放在状态里，也没法压缩复杂度。
下面是 Pisinger 最天才的想法：
于是我们来考虑记录可以删除的前缀。
\(f_{i,j}\) 表示前 \(i\) 个数，和 \(j\) 的最大可删除前缀（保证是满的）的长度！
(若和无法为 \(j\) 则设为 \(-1\))
设初始集合为 \(a_1\dots a_x\)。
初始值为
\(f_{x,a_k} = x\)。
考虑转移：
加入一个数
\[f_{i,j} = \max\{f_{i-1,j},f_{i-1,j-a_i}\} \]这很好理解——加入一个数就是普通的背包，求 \(\max\) 形式。
\[f_{i,j - a_k} = \max \{f_{i,j-a_k} , k - 1\} \space (1\leq k \leq f_{i,j}) \]循环顺序为从大到小做（删了这个数还可能删下一个数）。
虽然有些抽象，但是还是比较好理解：枚举一个可以删去的数字——然后删掉，转移。
但是这样还是 \(O(n^2A)\) 的啊——确实，因为要删很多不同的数。
所以我们给 \(k\) 设置下界 \(f_{i-1,j}< k \leq f_{i,j}\) 。
因为之前能删除的已经考虑过了——删除某些数后转移到了另一个值，所以我们只用考虑之前没考虑过的值即可了！因为 \(f\) 值对于每一个固定的和都是不减的，所以复杂度为 \(O(nA)\)！
删前缀为什么对？
考虑最终状态下的后半部分选入的集合一定被 dp 决策考虑了，而前面每步一定删除到了能删除的最大位置（这个前缀一定能被拆成若干段删除或不删除的区间），如果存在合法方案，一定会被这个过程包含在内。
想看正确性严谨的证明可以去翻论文。
代码并不复杂，即使需要构造方案也可以在 20 行之内完成，在 OI 中可能有用。
标签：顺序,删除,从洛谷,值域,复杂度,leq,子集,加总,考虑 From： https://www.cnblogs.com/Dreamerkk/p/18240465