contents
收錄於 批改娘 20005. 0/1 Knapsack Problem。之所以有機會談到這個問題,其原因於早期的背包問題,大多都是用 branch-and-bound 算法來完成,也因此學弟課程出了這一份作業,大部分的測資,使用 branch-and-bound 能跑得比一般記憶體化 DP 快上非常多。當然,作為一個 Morris(?) 怎能允許這樣的事情發生。
現在回顧一下背包問題的模型吧!
輸入格式
每組測資第一行包含兩個正整數,分別代表背包大小 $M$ ($\leq 5×10^6$) 和物品個數 $N$ ($\leq 1000$),下一行開始每行包含兩個正整數,分別代表物品價值 $P_i$ ($\leq 10^5$)和物品重量 $W_i$ ($ \leq 10^5$)。
輸出格式
對於每組測資,請輸出最大收益。
範例輸入 1
|
|
範例輸出 1
|
|
範例輸入 2
|
|
範例輸出 2
|
|
Solution
Branch-and-bound
bound knapscak problem 古耕竹同學提供
如果物品可以被切割,那麼可以利用物品的 CP 值 ($\textit{cp}_i = p_i/w_i$)排序,使用貪心算法在 $O(N \log N)$ 找到最佳解。然而,背包問題在於物品只能挑或不挑,一旦無法切割物品,那麼貪心算法無法將剩餘的部分填滿,進而可能產生更好的一組解填滿剩餘部分。
想要更快嗎?多看論文且實作它吧!
branch-and-bound 基本核心操作為
- 按照 CP 值由大到小排序
- 貪心法最佳解 $\textit{bound}$
- 進行深度優先搜索,優先挑 CP 值大的入選
- 當前挑選方案最佳解 $g$ + 剩餘物品使用貪心法最佳解 $g$ 小於等於當前最佳解 $\textit{bound}$,則退出搜索。
- 更新 $\textit{bound} = \max(\textit{bound}, g)$
- 選擇加入 或 不加入 (註:學弟說我的某些測資,通通優先不選可以快個數十倍)
參考代碼
|
|
結論
branch-and-bound 空間複雜度只跟 $N$ 有關,使用記憶體空間小,相較於記憶化搜索有較少的 cache miss,速度取決於搜索順序。對於同一 CP 的等價處理薄弱,一遇到這種情況,搜尋時間瞬間指數次方上去,可以等個昏天暗地。
Dynamic Programming
前言
請不要忘記背包問題屬於 NP-Complete,我們能做的事情只能優化計算,最慘的情況仍要面對,優化常數是可以努力的方向,讓我們嘗試變得更快吧。
基礎寫法解說請參考 DJWS - Bounded Knapsack Problem 的說明。
從定義上,我們通常會宣告 dp[i][j]
表示放入前 $i$ 個物品時,總共最多為 $j$ 的最大價值為何。這樣空間宣告使用 $\mathcal{O}(NW)$。在實作上,我們可以藉由運算順序將空間降為 $\mathcal{O}(W)$。因此,寫出以下代碼並不難
|
|
優化初夜
從實際運行上,我們可以發現每次跑 $\mathcal{\theta}(W)$ 非常浪費,只需要跑 $\min(W, \sum w_i)$ 即可。因此,第一份計算量優化如下
|
|
計算邊界優化通常可以達到 2x 加速
如此一來,在數量多權重小時,剛啟動的效能時可以賺到非常多。然而,不乏第一次就給權重的大的,目標最小化 $\sum \text{sum}_i$,從數學觀念很明顯地瞭解,只要一開始將權重 $w_i$ 由小到大排序即可,這樣能保證最小化計算量!
|
|
數學使得我們更進一步,達到 1.5x 加速
優化二夜
經由平行的訓練,也許我們可以更往上一層優化。
接下來,打算把物品拆成兩堆,再利用優化初夜學到的技巧,就能引爆更多計算邊界優化。如果拆成三堆以上,合併操作變得相當複雜,當只有兩堆時,保證合併效能一定在 $\mathcal{\theta}(W)$ 完成。
如何合併兩堆的計算結果,假設 dp1[i]
表示其中一堆重量小於等於 $i$ 的最佳解,同理 dp2[j]
的計算結果。
當要湊出重量為 $W$ 的最佳解時,窮舉其中一堆的重量 $i$ 維護其中一堆的前綴最大值 $j$,相當於使用掃描線算法在線性時間內合併。合併操作如下:
|
|
Divide-and-Conquer,使得我們更快再更快!達到 1.5 加速
然而,優化問題將轉移到最佳分堆策略,好的分堆策略將使得計算量下降更多。目標分兩堆,使得 $\sum \text{sum1}_i + \sum \text{sum2}_i$ 最小化。明顯地,由小到大排序物品重量,依序將物品放到總和最小的那一堆即可。最後,我們整合每一夜的結果如下:
一個好的分堆,達到 1.2x 加速
相信在不久之後,還有更好的優化策略,也許不是延伸,而是全新的面貌。
|
|