完全背包问题 —— 贪心优化 DP 范围

题意： 现在有 2n+1 个物品（n≤300），体积分别为 −n,−n+1,…,−1,0,1,…,n，第 i 个物品有 ai 个，求选出恰好 S 的总体积最多能选几个物品。

第一步：缩小值域。

不妨设 ∑ai>=S，否则将所有数取反。

这时先选完所有的负数，然后不断选正数直至和恰好不超过 S，则此时的和应该属于 [S−n,S]，值域范围被缩小了。

第二步：缩小状态

容易证明，从当前状态直至目标状态，必然存在一个操作序列，使得在任意时刻当前的和属于 [S−n,S+n]。

第三步：缩小物品数

又可以发现，如果存在两个时刻当前时刻的和相同，则这两个时刻之中的操作都是无用的，并且可以证明这一番无用操作一定会减小你所选出的物品数。于是你最多进行 2n+1 次改变。

每次改变至多变化 O(n)，因此 dp 值域 O(n2)，时间复杂度即为 O(n3)。