看了 ShanLunjiaJian 關於這個問題的文章，是完全沒看懂，沙東隊爺的中樞神經核心設定把我偏序了。叉姐在下面提了個論文，論文找不到資源，誰搞到了可以 Q 我一份之類的拜謝了。然後找到了這個可能是閱讀筆記或者是翻譯的的東西，這下算是看懂了。
感覺還是很有意思，對於 DP 的狀態設計、優化思路等都有很大啟發，所以寫一下。
ShanLunjiaJian 把這個叫做 Knapsack，我是要批判的，因為感覺上是帶不了權的啊，這不是Knapsack！
那麼描述一下這個問題：給定 \(n\) 個物品，每個物品有一個正整數重量 \(w_i\)，保證 \(1\le w_i\le 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 = \sum\limits_{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\)。轉移如下：
整體按照 \(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)\)！我們成功了！
有人問有什麼應用？我不知道啊。這麼基礎的東西一定有很多應用前景吧！（心虛）