前言
看了 ShanLunjiaJian 关于这个问题的文章，是完全没看懂，沙东队爷的中枢神经内核配置把我偏序了。叉姐在下面提了个论文，论文找不到资源，谁搞到了可以 Q 我一份之类的拜谢了。然后找到了这个可能是阅读笔记或者是翻译的的东西，这下算是看懂了。
感觉还是很有意思，对于 DP 的状态设计、优化思路等都有很大启发，所以写一下。
（有单个物品重量限制的）Subset Sum 问题
ShanLunjiaJian 把这个叫做 Knapsack，我是要批判的，因为感觉上是带不了权的啊，这不是Knapsack！
那么描述一下这个问题：给定 (n) 个物品，每个物品有一个正整数重量 (w_i)，保证 (1le w_ile V)，其中 (V) 是所谓的重量限制。现在给一个容量 (C)，取这些物品的一个子集，使得重量和不能超过这个容量，然后要求物品总重量的最大值，也就是让浪费的容量最小。
低论
这个问题显然有一个做法，叫做把它当作一个普通 Knapsack 问题，时间复杂度 (Theta(nC))。那么有意义的 (C le nV)。所以其实上界是 (n^2V)。现在我们有高论！可以做到 (Theta(nV))。
高论
首先这个问题有一个经典贪心做法，叫做给所有元素从小到大排个序，然后选一个前缀使得再多选一个就会超过容量限制。这个做法当然是错的，但是可以基于它给出的这个既有选择方法去做调整，那么这样一来，剩余容量就是 (mathrm O(V)) 的（如果大于 (V) 就一定可以再多选一个，矛盾了），很可做！
现在我们面临的问题是什么呢？我们的 DP 可能出现负数重量了（因为要支持取消选择一些原本选了的物品），这种条件下，要去维持我的剩余容量始终保持 (mathrm O(V))，是有一点难度的。怎么办呢？
考虑一个直觉，是不是可以这样去操作：当试图去取消一个原先选的物品（也就是选负数）的时候，一定要让当前容量是超额的；当去选正数的时候，一定要让当前容量是不满的。考虑最优解是不是一定能用这种方式构造出来——显然是可以的。证明可以这样想，假设我从贪心生成的“基础解”开始，按照某个顺序去把它修正成最优解，是不是每一步都一定能按照上述规则操作。那么可以这样想：如果现在容量是超额的，但是不存在某个元素使得“最优解中没选它，当前解中选了它”，那么最优解选择的集合一定包含当前解，它的容量就一定也是超额的，矛盾，所以一定有办法去进行操作。反之亦然，因此按照这样的规则操作，必然能得到某种最优解。更棒的是，在这样操作的过程中，剩余容量始终在 ([-V, V]) 以内！真是好极了，接下来只需要基于这种构造方案来 DP 就可以了。
先设计一个朴素 DP。设贪心得到的分界点为 (p)，使得目前选择的集合是标号 (le p) 的物品，(S_0 = sumlimits_{i = 1}^{p} w_i)。那么设 (g_{i, j, k}) 表示右边决策到 (i)，左边决策到 (j)，当前剩余容量为 (k in [-V, V]) 的方案是否存在。这个 DP 复杂度是 (Theta(n^2V))，真是一点优化效果都没有！但是这个东西的进一步改造非常方便，这就是下一步的想法。
注意到这是一个值为 Boolean 类型的 DP，如果发现某一维具有单调性，那么就可以压缩掉这维。可以观察到：如果 (g_{i, j, k} = 1)，那么对于任何 (t le j)，都有 (g_{i, t, k} = 1)——毕竟在左侧做出更多决策一定不会使可达集合变小。那么可以设 (f_{i, k} = max{0 le j le p | g_{i, j, k} = 1})。如果不存在这样的 (j)，设为 (-1)。那么 DP 的初始条件是 (f_{p+1, S_0} = p)。转移如下：
f_{i+1, k + w_i} gets f_{i, k}, & k le 0 & (1)
f_{i+1, k} gets f_{i, k}, & text{any} & (2)
f_{i, k – w_t} gets t – 1; & k ge 0 land t le f_{i, k} & (3)
end{cases}
]
整体按照 (i) 递增转移，每个 (i) 按照 (k) 递减的方向做转移 (3) 即可。时间复杂度是 (Theta(n^2V))，真是一点优化效果都没有！但是这个 DP 已经是 2D-1D 的了，进一步改造非常方便，这就是下一步的想法。
注意到只有转移 (3) 的复杂度不对，而这个转移很大程度上是重复的——某些转移过程，在 (i = a) 可以做，在 (i = a – 1) 同样可以做。那么可以尝试去掉这些转移，让本质相同的转移在最小的可以进行的 (i) 处去进行。注意到对于某个特定的 (k)，关于某个特定的 (t) 的转移能否进行，只和 (f_{i, k}) 是否足够大有关，而我们有单调性 (f_{i, k} le f_{i+1, k})，这是因为转移 (2) 的存在。所以转移 (3) 的条件可以改为 (k ge 0 land f_{i-1, k} le t le f_{i,k})。这样一来，某个特定 (k) 对总复杂度的贡献是 (mathrm O(n)) 的，所以总复杂度就变成了 (Theta(nV))！我们成功了！
后记
有人问有什么应用？我不知道啊。这么基础的东西一定有很多应用前景吧！（心虚）
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
什么是协程 说到协程，我们先了解什么是异步，异步简单说来就是，我要发起一个调用，但是这个被调用方（可能是其它线程，也可能是IO）出结果需要一段时间，我不想让这个调用阻塞住调用方的整个线程，因此传给被调用方一个回调函数，被调用方运行完成后回调这个回调函数就能通知…
