收錄於 批改娘 20008. Fast Multiple Knapsack Problem
之所以出了這一題，源自於實驗室另一名同學跑實驗太久，進而撰寫優化程序。聽說原本跑了十分鐘的實驗，改善後提升了到一分鐘跑完。
輸入格式
每組測資第一行包含兩個正整數，分別代表背包大小 $M$ ($\leq 10^6$) 和物品個數 $N$ ($\leq 1000$)，下一行開始每行包含兩個正整數，分別代表物品價值 $P_i$ ($\leq 10^3$)、物品重量 $W_i$ ($ \leq 10^5$) 以及物品最多可以挑 $C_i$ 個 ($\le 100$)。
輸出格式
對於每組測資，請輸出最大收益。
範例輸入 1
|
|
範例輸出 1
|
|
Solution
不管是 0/1 背包或者多重背包，兩者都屬於 bounded knapsack problem 問題。即便如此，優化上仍有些許的不同，請讓我緩緩道來。
在此之前，您必須先理解上一篇《淺談背包問題 (0/1 Knapsack Problem) 優化那些事》的部分，不然會造成閱讀上的困難。
多重背包有一個二進制優化，也就是當物品限制最多拿 $C$ 個時，我們可以利用二進制組合的方式，轉換到 0/1 背包問題，因此我們會得到新的 $N \log C$ 個物品跑一次 0/1 背包，因此複雜度落在 $O(N \log C \; W)$
然而，從公式定義上，在好幾年前的論文中，使用斜率優化降到 $O(N \; W)$，推倒過程如下，
$j = k \; w_i + r, \; 0 \le r \le w_i - 1$ $$\begin{align*} dp[i][j] &= \max\left\{dp[i-1][j], dp[i-1][j-w_i]+p_i, \cdots, dp[i-1][j-c_i \; w_i] + c_i \; p_i\right\} \\ &= \max\left\{dp[i-1][k \; w_i + r], dp[i-1][(k-1) \; w_i + r] + p_i, \cdots , dp[i-1][(k-c_i) \; w_i + r] + c_i p_i\right\} \\ &= \max\left\{dp[i-1][k \; w_i + r] - k \; p_i, dp[i-1][(k-1) \; w_i + r] + (k-1) \; p_i, \cdots , dp[i-1][(k-c_i) \; w_i + r] - (k-c_i) p_i\right\} + k \; p_i\\ \end{align*}$$隨著式子的轉移，我們發現每一個取值將不依賴相對位置，只跟自身的位置有關，那麼可以使用單調堆 (monotone queue) 運行 $O(1)$ 的 sliding windows 查找極值。最後，將相同餘數分堆處理，單調堆中最多存在 $O(c)$ 個元素。
優化初夜
如果只使用二進制優化，套上我們的 0/1 優化方案，將有大幅度地提升。
加入 0/1 背包的優化策略，再套上最簡單的斜率優化算法，得到下面的程式。這裡很懶惰地，由於單調堆最多入隊 $W$ 次，不外乎地直接只用大小為 $W$ 的方式實作。
|
|
不幸地，相較於一般的斜率優化寫法，並沒有太大的改善。
優化二夜
運行 sliding windows 操作時，前 $c$ 次，是不會進行 pop_front() 操作的，因此把迴圈分兩堆處理，增加 branch predict。以及在乘數運算上，使用強度減少 (strength reduction) 的技術，將乘法換成加法。
只能些許地改善 5% 的效能。
|
|
優化三夜
後來發現，sliding windows 滑動時，我們常常看前看後，因此常常會發生 cache miss，因為他要跳躍一大段記憶體空間查找數值，所以可以考慮花點操作將極值放在 stack 上，視為一種 software cache 來加速，來減少 cache miss 的懲罰。
接著，在迴圈邊界比較時，我們可以算得更精準些，回到一般的 i++ 的 format pattern，讓編譯器幫我們做常見的迴圈優化。
改善了 10% 效能
|
|
優化四夜
儘管上面使用的 software cache 的方式減少 cache miss，但 DP table 仍與數據結構的記憶體位置相當遙遠，為了使他們貼近，應使用環狀隊列的實作，空間從 $O(W)$ 將到 $O(N)$，實作時，將大小限制在 $2^k$，方便運行時使用 AND 運算取代耗時的模數運算。
由於限制個數分佈上，很容易造成貪心算法有解，因此先跑一次貪心，如果貪心沒辦法達到剛好大小，那麼再跑 DP 找解。DP 找解時，可以將物品嘗試進行二進制轉換，將等價物品合併，來觸發計算邊界的優化。完成的程序如下：
最終加速，改善 10%，期待你我的分享增進。根據鴿籠原理，cp 直種類不多時，可以高達 10 倍以上的加速。
|
|