)
01背包問題是我接觸算法這么多年最常拿來測試新思路的“試金石”。它表面簡單到一句話就能說清楚每個物品要么裝進背包、要么不裝在總重量不超過背包容量的前提下讓總價值盡可能大?？梢坏┪锲窋?shù)量超過幾十個暴力枚舉立刻變成天文數(shù)字貪心算法快是快卻經(jīng)常在最后一刻給出一個不是最優(yōu)的答案動態(tài)規(guī)劃在容量很大的時候內(nèi)存和時間又會雙雙爆炸。我第一次認真研究分支定界算法Branch and Bound就是被這樣一組數(shù)據(jù)逼的物品數(shù)量不算大但背包容量到了千萬級別動態(tài)規(guī)劃根本塞不下貪心又無法保證最優(yōu)。后來把分支定界吃透才明白這類問題的核心不是“遍歷所有方案”而是如何盡可能少地遍歷。這篇文章從問題建模講起逐步拆解分支定界的三件套——分支、定界、剪枝然后給出一份可以直接跑的 Python 實現(xiàn)最后聊聊我在不同規(guī)模算例上的實測體會以及它和動態(tài)規(guī)劃、回溯法之間到底該怎么選。1. 為什么01背包看起來簡單卻容易在數(shù)據(jù)量面前翻車1.1 問題本質(zhì)與數(shù)學(xué)建模先把問題形式化。給定 n 個物品第 i 個物品的重量是 w_i、價值是 v_i背包容量為 C。引入 0-1 決策變量 x_ix_i 1 表示裝入x_i 0 表示不裝那么模型就是最大化Σ v_i * x_i 約束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}注意這里“0-1”是核心它和“分數(shù)背包”有本質(zhì)區(qū)別。分數(shù)背包允許把一個物品切開只裝一部分所以貪心按價值密度從高到低裝就行了。而 01 背包不允許切割一個物品只有“整件裝”和“整件不裝”兩種狀態(tài)這就導(dǎo)致貪心失效你可能為了裝下一個密度很高的物品被迫放棄一堆密度稍低但總價值更大的組合。這種問題的復(fù)雜度屬于 NP 難。從組合數(shù)學(xué)的角度看n 個物品的選擇方案一共有 2^n 種。n 30 時是十億級別n 50 時 2^50 已經(jīng)超過一千萬億普通機器上直接枚舉是絕對跑不完的。1.2 貪心失敗現(xiàn)場與動態(tài)規(guī)劃的內(nèi)存困境我見過不止一個初學(xué)者寫完貪心代碼之后對著結(jié)果發(fā)呆。舉個反例背包容量 10三個物品分別為 (重量, 價值) (6, 6)、(5, 5)、(5, 5)。按價值密度排序全部一樣貪心先裝第一個剩余容量 4裝不下任何剩下的總價值 6。可實際上裝后兩個總價值是 10重量剛好也是 10。這就是 01 背包和分數(shù)背包最大的區(qū)別它不是一個“按比例分配”的問題而是一個“組合取舍”的問題。動態(tài)規(guī)劃能保證最優(yōu)時間復(fù)雜度 O(nC)空間可以滾動到 O(C)。問題是這個復(fù)雜度里的 C 是背包容量不是物品個數(shù)。我實際遇到過 n 500、C 5000000 的輸入500 × 500 萬就是 25 億次操作內(nèi)存哪怕用滾動數(shù)組也要 500 萬 × 4 字節(jié)約 20MB時間卻要好幾秒甚至更久。當容量繼續(xù)放大到億級DP 基本就廢了。分支定界算法在這個場景下就顯得特別有價值它不依賴容量 C 的大小核心消耗取決于搜索樹的節(jié)點數(shù)。只要上界函數(shù)設(shè)計得好、剪枝剪得及時很多大規(guī)模實例在極短時間就能出最優(yōu)解。這也是我決定深入實現(xiàn)它的原因。2. 分支定界的三件套分支、定界與剪枝的完整邏輯2.1 解空間樹把“選/不選”鋪成一棵二叉樹分支定界的第一步是把所有可能方案組織成一棵樹。樹的每一層對應(yīng)一個物品的決策節(jié)點從根節(jié)點出發(fā)左分支表示“裝入當前物品”右分支表示“不裝當前物品”。走到葉子節(jié)點就得到一組完整的 0-1 選擇方案。n 個物品的解空間樹一共有 2^(n1) - 1 個節(jié)點葉子數(shù)是 2^n。直接遍歷這棵樹就是回溯法復(fù)雜度指數(shù)級。分支定界和樸素回溯的本質(zhì)區(qū)別在于回溯法把所有葉子都走一遍才能確定最優(yōu)解而分支定界在每個內(nèi)部節(jié)點先估算“如果繼續(xù)往下走最高能拿到多少價值”一旦這個估算值比當前已知最優(yōu)解還要差就果斷砍掉整個子樹根本不用進去。2.2 定界的幾何直覺先假設(shè)“能切開”再慢慢收緊分支定界里上界函數(shù)是整個算法的靈魂。常見的做法是把 01 背包“松弛”成連續(xù)背包問題允許當前節(jié)點后面的物品按任意比例裝入。因為約束放寬了松弛問題的最優(yōu)解一定不小于原問題任何一個可行解的價值所以它可以作為原問題的合法上界。這個上界還有一個特別好的性質(zhì)連續(xù)背包問題用貪心就能解。把剩余物品按價值密度從高到低排好能整件裝的先整件裝裝到最后一個物品時如果剩余容量不夠就按比例取一部分。算出來的總價值就是當前節(jié)點繼續(xù)往下探索的價值天花板。更有意思的是整數(shù)取整。如果所有價值和重量都是正整數(shù)那么任意一個整數(shù)可行解的價值必然是整數(shù)而上界如果是 13.67那它真正的整數(shù)上界最多是 13。把上界向下取整在實際剪枝中往往能多砍掉相當一部分節(jié)點。2.3 三個可以剪枝的地方別漏掉任何一個我用一個具體例子演示。假設(shè) 4 個物品(重量, 價值) (2, 3)、(3, 4)、(4, 5)、(5, 8)背包容量 9。所有方案里最優(yōu)的是裝物品 3 和物品 4總重量 9總價值 13。首先按價值密度從大到小排序排序后順序是物品 4密度 1.6、物品 1密度 1.5、物品 2密度 1.33、物品 3密度 1.25。根節(jié)點的上界按密度裝滿 9 容量物品 4 整裝、物品 1 整裝剩 2 容量只能裝 2/3 個物品 2上界 8 3 4×2/3 ≈ 13.67取整為 13。初始最優(yōu)解 best_value 設(shè)為 0開始深度優(yōu)先搜索。整個過程可以簡化成下面這棵文本樹根節(jié)點上界13 ├─ 左裝物品4重量5價值8上界13 │ ├─ 左裝物品1重量7價值11上界13 │ │ └─ 右不裝物品2之后只能走到價值11best更新為11 │ └─ 右不裝物品1重量5價值8上界13 │ ├─ 左裝物品2重量8價值12best更新為12 │ └─ 右不裝物品2重量5價值8 │ └─ 左裝物品3重量9價值13best更新為13 └─ 右不裝物品4上界 345 1212 ≤ best13剪枝可以看到右分支在根節(jié)點就被砍掉了因為不管后面怎么選價值都不可能超過 12。整個搜索只訪問了 12 個節(jié)點而樸素回溯會訪問全部 31 個節(jié)點。當 n 變大這種差距會被指數(shù)級放大。3. 上界函數(shù)的底層思考連續(xù)背包松弛為什么能用、怎么用3.1 線性規(guī)劃松弛允許“半個物品”的妙處很多人第一次看到連續(xù)背包松弛都會有一個疑問明明 01 背包不允許裝半個物品為什么拿“允許裝半個”的模型來當上界不會給出錯誤的剪枝判斷關(guān)鍵在于“上界”的性質(zhì)。我們要保證一件事任何從當前節(jié)點出發(fā)的完整方案其價值都不可能超過上界函數(shù)算出來的值。連續(xù)背包問題的可行域比 01 背包更大所有整數(shù)可行解都是松弛問題的可行解。因此松弛問題的最優(yōu)值一定是整數(shù)問題最優(yōu)值的上界這個邏輯是嚴格成立的。用一句話概括放寬約束只會讓最優(yōu)值變大絕不會變小所以它是一個“不會漏掉最優(yōu)解”的天花板。連續(xù)背包問題的貪心最優(yōu)性也可以用交換論證來理解假設(shè)有兩個物品 A 和 BA 的密度比 B 高。如果一個可行解里裝了 B 的一部分重量 d卻在 A 還沒裝滿時留有空位那么把 d 這部分重量換成等重的 A重量不變、價值更高。反復(fù)做這種交換最終的形態(tài)必然是密度從高到低裝滿所以貪心順序正確。3.2 從13.67到13取整技巧帶來的額外剪枝力取整技巧非常實用但有兩件事必須注意。第一只有所有物品的價值、重量都是整數(shù)時才能放心對 bound 向下取整。整數(shù)可行解的價值累加后必然是整數(shù)而連續(xù)松弛上界哪怕算出 13.67實際上你最多能湊出的整數(shù)價值也不會超過 13?？扇绻锲穬r值本身是浮點數(shù)直接 int() 可能會把上界截到一個不可達的下方造成誤剪枝。我在實現(xiàn)里默認所有輸入都是正整數(shù)所以會用int(bound(...)) best_value作剪枝條件如果碰到浮點價值改成bound(...) best_value 1e-9更穩(wěn)妥。第二取整時必須向下取整不能四舍五入。13.67 四舍五入成 14 之后上界被抬高了剪枝條件變得更難滿足等于削弱算法效果向下取整才是安全的緊化。3.3 上界計算的代碼實現(xiàn)要點上界函數(shù)的實現(xiàn)邏輯很直白def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper一個容易被忽略的性能優(yōu)化當剩余容量還能裝下從 start 到末尾的所有物品時按密度貪心并沒有意義此時上界就是當前價值加上剩余物品價值總和。這行判斷可以用后綴和數(shù)組提前算好雖然能省的時間不多但在節(jié)點數(shù)上百萬時能減少不少浮點乘除和循環(huán)開銷。另外要強調(diào)上界函數(shù)計算越緊剪枝效果越好但計算量也會增大。連續(xù)背包松弛是目前性價比最高的選擇它只需要一次線性掃描還能配合我們已經(jīng)做好的密度排序直接使用不需要額外數(shù)據(jù)結(jié)構(gòu)的維護。4. 一份能跑的Python求解器實現(xiàn)與核心代碼逐段拆解4.1 預(yù)處理為什么必須先按價值密度排序分支定界對物品做密度降序排序有三個好處一是上界函數(shù)計算連續(xù)背包解時天然依賴密度從高到低的順序排序之后直接按順序掃描即可。二是在搜索過程中先考慮密度高的物品更容易在早期形成質(zhì)量較好的可行解。比如根節(jié)點左邊分支裝上密度最高的物品往往很快就逼近最優(yōu)值best_value 提升得快后續(xù)剪枝條件更容易滿足。三是排序不會改變最優(yōu)解本身因為解空間本質(zhì)上是在枚舉所有 0-1 組合順序調(diào)整并不影響組合的完整性。我在代碼中使用(weights[i], values[i], i)三元組保存原始下標排序時只排三元組列表這樣排序后依然能回溯每個物品的原始位置最終構(gòu)造出正確的選擇掩碼。4.2 深度優(yōu)先搜索與剪枝代碼完整求解器如下def solve_01knapsack_bnb(weights, values, capacity): n len(weights) items sorted( [(weights[i], values[i], i) for i in range(n)], keylambda x: x[1] / x[0], reverseTrue ) best_value 0 best_mask [0] * n node_count 0 def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper def dfs(idx, cur_w, cur_v, chosen): nonlocal best_value, best_mask, node_count node_count 1 if cur_v best_value: best_value cur_v best_mask [0] * n for orig in chosen: best_mask[orig] 1 if idx n: return if int(bound(idx, cur_w, cur_v)) best_value: return w, v, orig_i items[idx] if cur_w w capacity: dfs(idx 1, cur_w w, cur_v v, chosen [orig_i]) dfs(idx 1, cur_w, cur_v, chosen) dfs(0, 0, 0, []) return best_value, best_mask, node_count代碼里有一個容易被忽略的順序進入節(jié)點后先做“價值更新”再做“上界剪枝”。這樣設(shè)計是有意的。當遞歸從更深層返回到當前節(jié)點時全局 best_value 可能已經(jīng)被某個可行解刷新過了此時再算上界剪枝才有意義。如果先剪枝再更新部分子樹就可能被一個偏低的 best_value 錯誤放過導(dǎo)致整體搜索量變大。4.3 記錄最優(yōu)解從chosen列表到最終掩碼很多教程只返回最優(yōu)值不返回選中的物品集合這對實際項目來說不夠用。我用chosen列表保存從根到當前節(jié)點“裝入”的物品的原始下標每當找到一個更優(yōu)價值時就重新生成一個長度為 n 的全 0 掩碼把 chosen 里的下標都置為 1。這種方式邏輯清晰代價是每次更新最優(yōu)解都要 O(n) 復(fù)制數(shù)組。當 n 達到幾萬時頻繁更新可能拖慢速度。另一種做法是維護一個和物品數(shù)等長的選擇數(shù)組在遞歸中用“選/不選”原位更新葉子節(jié)點時統(tǒng)一拷貝一次。我推薦先跑通當前版本再根據(jù)性能瓶頸決定要不要優(yōu)化。4.4 標準算例演示用之前的例子驗證weights [2, 3, 4, 5] values [3, 4, 5, 8] capacity 9 value, mask, count solve_01knapsack_bnb(weights, values, capacity) print(最優(yōu)價值:, value) print(選擇掩碼:, mask) print(物品原始下標:, [i for i, x in enumerate(mask) if x 1]) print(探索節(jié)點數(shù):, count)輸出應(yīng)該是最優(yōu)價值: 13 選擇掩碼: [0, 0, 1, 1] 物品原始下標: [2, 3] 探索節(jié)點數(shù): 12注意掩碼[0, 0, 1, 1]對應(yīng)原始物品 3 和物品 4總重量 4 5 9總價值 5 8 13。整個搜索只訪問 12 個節(jié)點遠小于 31 個節(jié)點的全遍歷量。5. 大規(guī)模實測分支定界、動態(tài)規(guī)劃與回溯法的選型邊界5.1 節(jié)點數(shù)與上界質(zhì)量的關(guān)聯(lián)分支定界的實際表現(xiàn)高度依賴數(shù)據(jù)特征我把它分成兩類典型場景。一類是“強相關(guān)”數(shù)據(jù)。價值與重量強相關(guān)比如價值 2 × 重量 隨機小擾動。這種情況下連續(xù)背包松弛算出的上界和真正整數(shù)最優(yōu)解非常接近剪枝異常迅猛。我實測過 n 200、容量 5000 的強相關(guān)數(shù)據(jù)很多情況下節(jié)點數(shù)只有幾千毫秒級出結(jié)果。另一類是“弱相關(guān)”數(shù)據(jù)。價值和重量基本獨立隨機生成比如重量隨機取 1 到 100價值隨機取 1 到 200。此時連續(xù)背包松弛的上界會明顯虛高剪枝能力大幅下降節(jié)點數(shù)可能膨脹到幾十萬甚至百萬級。n 60、容量 1500 的弱相關(guān)數(shù)據(jù)就要做好它跑好幾秒的心理準備而同樣數(shù)據(jù)用動態(tài)規(guī)劃 O(60×1500) 只要一個 O(nC) 小表就解決了。所以分支定界并不是“更快的最優(yōu)求解器”它是“在某些數(shù)據(jù)分布下特別高效的最優(yōu)求解器”。動手之前先看一下你的數(shù)據(jù)是重相關(guān)還是弱相關(guān)才能判斷要不要選它。5.2 分支定界、動態(tài)規(guī)劃、回溯暴力的適用邊界對照我把三種精確求解方法放在一張表里比較方法時間復(fù)雜度空間復(fù)雜度強項明顯短板回溯暴力最壞 O(2^n)O(n)實現(xiàn)最簡單幾乎不剪枝n 30 就吃力分支定界平均遠小于 2^n最壞 O(2^n)O(n)遞歸棧不依賴容量數(shù)據(jù)強相關(guān)時極快弱相關(guān)數(shù)據(jù)可能退化指數(shù)級動態(tài)規(guī)劃O(nC)O(C) 可滾動穩(wěn)定可預(yù)測小容量場景最優(yōu)容量 C 大時內(nèi)存和耗時爆掉從工程角度我一般這樣選型容量 C 和物品種類 n 都在可接受范圍直接上 DP穩(wěn)定省心。C 特別大、但物品數(shù)據(jù)有明顯密度差異上分支定界。數(shù)據(jù)是弱相關(guān)隨機且 n 很大那就別硬剛精確解考慮啟發(fā)式近似算法更現(xiàn)實。5.3 我踩過的一個遞歸大坑用 Python 寫 DFS 分支定界時有一個隱藏地雷遞歸深度。n 達到 1000 以上時默認遞歸上限很容易爆出RecursionError。解決辦法有兩個一是在腳本開頭設(shè)置sys.setrecursionlimit(10000)二是改用顯式棧。顯式棧還有一個額外好處棧節(jié)點可以動態(tài)排序方便實現(xiàn)后面要說的最佳優(yōu)先搜索。不過代價是代碼復(fù)雜度明顯上升。如果你只是處理幾百個物品遞歸版本足夠沒必要一開始就寫顯式棧。6. 進階玩法Best-First搜索、下界強化與并行注意點6.1 最佳優(yōu)先搜索優(yōu)先處理最有希望的節(jié)點深度優(yōu)先搜索的優(yōu)點是內(nèi)存小但它的“搜索路線”有時很盲目明明某個節(jié)點的上界非常高卻因為遞歸路徑的關(guān)系被排到很晚才處理反而一些上界很低的節(jié)點卻因為出現(xiàn)在遞歸路徑上被優(yōu)先擴展了。Best-First 策略用一個優(yōu)先隊列替代遞歸棧每次取出上界最高的節(jié)點擴展。這樣做的直接好處是算法會非?？斓刈叩揭粭l高質(zhì)量路徑并迅速刷新全局最優(yōu)解。全局最優(yōu)解變緊之后其他節(jié)點的剪枝條件也就更容易滿足。代價是優(yōu)先隊列需要保存大量節(jié)點最壞情況下內(nèi)存會指數(shù)增長。我通常只在解空間特別大、且上界質(zhì)量參差不齊時使用 Best-First。6.2 下界強化起步時用一個好一點的初值很多實現(xiàn)把初始 best_value 設(shè)為 0這其實浪費了第一波剪枝機會。簡單的改進是先跑一遍貪心算法把一個可行解的價值作為初始下界。貪心解雖然不一定最優(yōu)但往往不會太差尤其強相關(guān)數(shù)據(jù)下可能已經(jīng)非常接近最優(yōu)值。這樣搜索一開始就有了一把還算緊的尺子剪枝效率立即提升。更激進的做法是在每個節(jié)點內(nèi)部再做一次局部貪心基于當前已選物品繼續(xù)往后挑選可行解得到一個更精細的下界。但節(jié)點內(nèi)部貪心會增加計算成本對于節(jié)點數(shù)已經(jīng)很少的強相關(guān)數(shù)據(jù)收益不大對于弱相關(guān)數(shù)據(jù)單純加一個啟發(fā)式下界也救不了虛高的上界。所以我的建議是先用全局貪心當初始下界跑一輪看效果再決定要不要加節(jié)點級啟發(fā)式。6.3 并行化的現(xiàn)實考量分支定界天然適合并行根節(jié)點的左右分支彼此獨立可以分給不同工作線程去搜索。工程上需要維護一個全局共享的 best_value任意工作線程發(fā)現(xiàn)更優(yōu)可行解就原子更新其他線程在剪枝判斷時讀取這個全局下界。但并行分支定界有一個典型的坑全局 best 更新可能有延遲某個線程在上界已經(jīng)能剪枝時因為讀到的 best 偏小白白多搜了一整棵子樹。要緩解這個問題可以讓工作線程定期同步全局 best同時在每個子樹搜索開始時重新讀取一次。實際經(jīng)驗是并行只能應(yīng)對“弱相關(guān)大實例”帶來的節(jié)點爆炸而且加速比并不線性很多時候 8 核只跑出 3 到 4 倍提升。如果節(jié)點數(shù)不大并行反而因為線程同步開銷變慢。我建議先把單核版本調(diào)到足夠好再考慮并行。最后分享兩個開發(fā)小技巧。第一實現(xiàn)分支定界時先寫一個完全不帶剪枝的回溯版配合小規(guī)模暴力枚舉或 DP 驗證正確性然后再加 bound 和剪枝一步一確認。第二步專注調(diào)試剪枝條件不然上界函數(shù)出錯時很難定位是“剪錯了最優(yōu)解”還是“搜索路徑本身有 bug”。第二調(diào)優(yōu)時把 node_count 打印出來觀察剪枝前后節(jié)點數(shù)的變化。如果加了剪枝之后節(jié)點數(shù)還和暴力幾乎一樣八成是上界太松或者排序沒生效這時候再回頭檢查上界函數(shù)比盲目加并行要有效得多。 01背包問題的高效求解：分支定界算法原理與Python實現(xiàn)
01背包問題是我接觸算法這么多年最常拿來測試新思路的“試金石”。它表面簡單到一句話就能說清楚每個物品要么裝進背包、要么不裝在總重量不超過背包容量的前提下讓總價值盡可能大?？梢坏┪锲窋?shù)量超過幾十個暴力枚舉立刻變成天文數(shù)字貪心算法快是快卻經(jīng)常在最后一刻給出一個不是最優(yōu)的答案動態(tài)規(guī)劃在容量很大的時候內(nèi)存和時間又會雙雙爆炸。我第一次認真研究分支定界算法Branch and Bound就是被這樣一組數(shù)據(jù)逼的物品數(shù)量不算大但背包容量到了千萬級別動態(tài)規(guī)劃根本塞不下貪心又無法保證最優(yōu)。后來把分支定界吃透才明白這類問題的核心不是“遍歷所有方案”而是如何盡可能少地遍歷。這篇文章從問題建模講起逐步拆解分支定界的三件套——分支、定界、剪枝然后給出一份可以直接跑的 Python 實現(xiàn)最后聊聊我在不同規(guī)模算例上的實測體會以及它和動態(tài)規(guī)劃、回溯法之間到底該怎么選。1. 為什么01背包看起來簡單卻容易在數(shù)據(jù)量面前翻車1.1 問題本質(zhì)與數(shù)學(xué)建模先把問題形式化。給定 n 個物品第 i 個物品的重量是 w_i、價值是 v_i背包容量為 C。引入 0-1 決策變量 x_ix_i 1 表示裝入x_i 0 表示不裝那么模型就是最大化Σ v_i * x_i 約束 Σ w_i * x_i ≤ C x_i ∈ {0, 1}注意這里“0-1”是核心它和“分數(shù)背包”有本質(zhì)區(qū)別。分數(shù)背包允許把一個物品切開只裝一部分所以貪心按價值密度從高到低裝就行了。而 01 背包不允許切割一個物品只有“整件裝”和“整件不裝”兩種狀態(tài)這就導(dǎo)致貪心失效你可能為了裝下一個密度很高的物品被迫放棄一堆密度稍低但總價值更大的組合。這種問題的復(fù)雜度屬于 NP 難。從組合數(shù)學(xué)的角度看n 個物品的選擇方案一共有 2^n 種。n 30 時是十億級別n 50 時 2^50 已經(jīng)超過一千萬億普通機器上直接枚舉是絕對跑不完的。1.2 貪心失敗現(xiàn)場與動態(tài)規(guī)劃的內(nèi)存困境我見過不止一個初學(xué)者寫完貪心代碼之后對著結(jié)果發(fā)呆。舉個反例背包容量 10三個物品分別為 (重量, 價值) (6, 6)、(5, 5)、(5, 5)。按價值密度排序全部一樣貪心先裝第一個剩余容量 4裝不下任何剩下的總價值 6。可實際上裝后兩個總價值是 10重量剛好也是 10。這就是 01 背包和分數(shù)背包最大的區(qū)別它不是一個“按比例分配”的問題而是一個“組合取舍”的問題。動態(tài)規(guī)劃能保證最優(yōu)時間復(fù)雜度 O(nC)空間可以滾動到 O(C)。問題是這個復(fù)雜度里的 C 是背包容量不是物品個數(shù)。我實際遇到過 n 500、C 5000000 的輸入500 × 500 萬就是 25 億次操作內(nèi)存哪怕用滾動數(shù)組也要 500 萬 × 4 字節(jié)約 20MB時間卻要好幾秒甚至更久。當容量繼續(xù)放大到億級DP 基本就廢了。分支定界算法在這個場景下就顯得特別有價值它不依賴容量 C 的大小核心消耗取決于搜索樹的節(jié)點數(shù)。只要上界函數(shù)設(shè)計得好、剪枝剪得及時很多大規(guī)模實例在極短時間就能出最優(yōu)解。這也是我決定深入實現(xiàn)它的原因。2. 分支定界的三件套分支、定界與剪枝的完整邏輯2.1 解空間樹把“選/不選”鋪成一棵二叉樹分支定界的第一步是把所有可能方案組織成一棵樹。樹的每一層對應(yīng)一個物品的決策節(jié)點從根節(jié)點出發(fā)左分支表示“裝入當前物品”右分支表示“不裝當前物品”。走到葉子節(jié)點就得到一組完整的 0-1 選擇方案。n 個物品的解空間樹一共有 2^(n1) - 1 個節(jié)點葉子數(shù)是 2^n。直接遍歷這棵樹就是回溯法復(fù)雜度指數(shù)級。分支定界和樸素回溯的本質(zhì)區(qū)別在于回溯法把所有葉子都走一遍才能確定最優(yōu)解而分支定界在每個內(nèi)部節(jié)點先估算“如果繼續(xù)往下走最高能拿到多少價值”一旦這個估算值比當前已知最優(yōu)解還要差就果斷砍掉整個子樹根本不用進去。2.2 定界的幾何直覺先假設(shè)“能切開”再慢慢收緊分支定界里上界函數(shù)是整個算法的靈魂。常見的做法是把 01 背包“松弛”成連續(xù)背包問題允許當前節(jié)點后面的物品按任意比例裝入。因為約束放寬了松弛問題的最優(yōu)解一定不小于原問題任何一個可行解的價值所以它可以作為原問題的合法上界。這個上界還有一個特別好的性質(zhì)連續(xù)背包問題用貪心就能解。把剩余物品按價值密度從高到低排好能整件裝的先整件裝裝到最后一個物品時如果剩余容量不夠就按比例取一部分。算出來的總價值就是當前節(jié)點繼續(xù)往下探索的價值天花板。更有意思的是整數(shù)取整。如果所有價值和重量都是正整數(shù)那么任意一個整數(shù)可行解的價值必然是整數(shù)而上界如果是 13.67那它真正的整數(shù)上界最多是 13。把上界向下取整在實際剪枝中往往能多砍掉相當一部分節(jié)點。2.3 三個可以剪枝的地方別漏掉任何一個我用一個具體例子演示。假設(shè) 4 個物品(重量, 價值) (2, 3)、(3, 4)、(4, 5)、(5, 8)背包容量 9。所有方案里最優(yōu)的是裝物品 3 和物品 4總重量 9總價值 13。首先按價值密度從大到小排序排序后順序是物品 4密度 1.6、物品 1密度 1.5、物品 2密度 1.33、物品 3密度 1.25。根節(jié)點的上界按密度裝滿 9 容量物品 4 整裝、物品 1 整裝剩 2 容量只能裝 2/3 個物品 2上界 8 3 4×2/3 ≈ 13.67取整為 13。初始最優(yōu)解 best_value 設(shè)為 0開始深度優(yōu)先搜索。整個過程可以簡化成下面這棵文本樹根節(jié)點上界13 ├─ 左裝物品4重量5價值8上界13 │ ├─ 左裝物品1重量7價值11上界13 │ │ └─ 右不裝物品2之后只能走到價值11best更新為11 │ └─ 右不裝物品1重量5價值8上界13 │ ├─ 左裝物品2重量8價值12best更新為12 │ └─ 右不裝物品2重量5價值8 │ └─ 左裝物品3重量9價值13best更新為13 └─ 右不裝物品4上界 345 1212 ≤ best13剪枝可以看到右分支在根節(jié)點就被砍掉了因為不管后面怎么選價值都不可能超過 12。整個搜索只訪問了 12 個節(jié)點而樸素回溯會訪問全部 31 個節(jié)點。當 n 變大這種差距會被指數(shù)級放大。3. 上界函數(shù)的底層思考連續(xù)背包松弛為什么能用、怎么用3.1 線性規(guī)劃松弛允許“半個物品”的妙處很多人第一次看到連續(xù)背包松弛都會有一個疑問明明 01 背包不允許裝半個物品為什么拿“允許裝半個”的模型來當上界不會給出錯誤的剪枝判斷關(guān)鍵在于“上界”的性質(zhì)。我們要保證一件事任何從當前節(jié)點出發(fā)的完整方案其價值都不可能超過上界函數(shù)算出來的值。連續(xù)背包問題的可行域比 01 背包更大所有整數(shù)可行解都是松弛問題的可行解。因此松弛問題的最優(yōu)值一定是整數(shù)問題最優(yōu)值的上界這個邏輯是嚴格成立的。用一句話概括放寬約束只會讓最優(yōu)值變大絕不會變小所以它是一個“不會漏掉最優(yōu)解”的天花板。連續(xù)背包問題的貪心最優(yōu)性也可以用交換論證來理解假設(shè)有兩個物品 A 和 BA 的密度比 B 高。如果一個可行解里裝了 B 的一部分重量 d卻在 A 還沒裝滿時留有空位那么把 d 這部分重量換成等重的 A重量不變、價值更高。反復(fù)做這種交換最終的形態(tài)必然是密度從高到低裝滿所以貪心順序正確。3.2 從13.67到13取整技巧帶來的額外剪枝力取整技巧非常實用但有兩件事必須注意。第一只有所有物品的價值、重量都是整數(shù)時才能放心對 bound 向下取整。整數(shù)可行解的價值累加后必然是整數(shù)而連續(xù)松弛上界哪怕算出 13.67實際上你最多能湊出的整數(shù)價值也不會超過 13?？扇绻锲穬r值本身是浮點數(shù)直接 int() 可能會把上界截到一個不可達的下方造成誤剪枝。我在實現(xiàn)里默認所有輸入都是正整數(shù)所以會用int(bound(...)) best_value作剪枝條件如果碰到浮點價值改成bound(...) best_value 1e-9更穩(wěn)妥。第二取整時必須向下取整不能四舍五入。13.67 四舍五入成 14 之后上界被抬高了剪枝條件變得更難滿足等于削弱算法效果向下取整才是安全的緊化。3.3 上界計算的代碼實現(xiàn)要點上界函數(shù)的實現(xiàn)邏輯很直白def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper一個容易被忽略的性能優(yōu)化當剩余容量還能裝下從 start 到末尾的所有物品時按密度貪心并沒有意義此時上界就是當前價值加上剩余物品價值總和。這行判斷可以用后綴和數(shù)組提前算好雖然能省的時間不多但在節(jié)點數(shù)上百萬時能減少不少浮點乘除和循環(huán)開銷。另外要強調(diào)上界函數(shù)計算越緊剪枝效果越好但計算量也會增大。連續(xù)背包松弛是目前性價比最高的選擇它只需要一次線性掃描還能配合我們已經(jīng)做好的密度排序直接使用不需要額外數(shù)據(jù)結(jié)構(gòu)的維護。4. 一份能跑的Python求解器實現(xiàn)與核心代碼逐段拆解4.1 預(yù)處理為什么必須先按價值密度排序分支定界對物品做密度降序排序有三個好處一是上界函數(shù)計算連續(xù)背包解時天然依賴密度從高到低的順序排序之后直接按順序掃描即可。二是在搜索過程中先考慮密度高的物品更容易在早期形成質(zhì)量較好的可行解。比如根節(jié)點左邊分支裝上密度最高的物品往往很快就逼近最優(yōu)值best_value 提升得快后續(xù)剪枝條件更容易滿足。三是排序不會改變最優(yōu)解本身因為解空間本質(zhì)上是在枚舉所有 0-1 組合順序調(diào)整并不影響組合的完整性。我在代碼中使用(weights[i], values[i], i)三元組保存原始下標排序時只排三元組列表這樣排序后依然能回溯每個物品的原始位置最終構(gòu)造出正確的選擇掩碼。4.2 深度優(yōu)先搜索與剪枝代碼完整求解器如下def solve_01knapsack_bnb(weights, values, capacity): n len(weights) items sorted( [(weights[i], values[i], i) for i in range(n)], keylambda x: x[1] / x[0], reverseTrue ) best_value 0 best_mask [0] * n node_count 0 def bound(start, cur_w, cur_v): remain capacity - cur_w upper cur_v i start while i n and items[i][0] remain: upper items[i][1] remain - items[i][0] i 1 if i n and remain 0: upper items[i][1] * (remain / items[i][0]) return upper def dfs(idx, cur_w, cur_v, chosen): nonlocal best_value, best_mask, node_count node_count 1 if cur_v best_value: best_value cur_v best_mask [0] * n for orig in chosen: best_mask[orig] 1 if idx n: return if int(bound(idx, cur_w, cur_v)) best_value: return w, v, orig_i items[idx] if cur_w w capacity: dfs(idx 1, cur_w w, cur_v v, chosen [orig_i]) dfs(idx 1, cur_w, cur_v, chosen) dfs(0, 0, 0, []) return best_value, best_mask, node_count代碼里有一個容易被忽略的順序進入節(jié)點后先做“價值更新”再做“上界剪枝”。這樣設(shè)計是有意的。當遞歸從更深層返回到當前節(jié)點時全局 best_value 可能已經(jīng)被某個可行解刷新過了此時再算上界剪枝才有意義。如果先剪枝再更新部分子樹就可能被一個偏低的 best_value 錯誤放過導(dǎo)致整體搜索量變大。4.3 記錄最優(yōu)解從chosen列表到最終掩碼很多教程只返回最優(yōu)值不返回選中的物品集合這對實際項目來說不夠用。我用chosen列表保存從根到當前節(jié)點“裝入”的物品的原始下標每當找到一個更優(yōu)價值時就重新生成一個長度為 n 的全 0 掩碼把 chosen 里的下標都置為 1。這種方式邏輯清晰代價是每次更新最優(yōu)解都要 O(n) 復(fù)制數(shù)組。當 n 達到幾萬時頻繁更新可能拖慢速度。另一種做法是維護一個和物品數(shù)等長的選擇數(shù)組在遞歸中用“選/不選”原位更新葉子節(jié)點時統(tǒng)一拷貝一次。我推薦先跑通當前版本再根據(jù)性能瓶頸決定要不要優(yōu)化。4.4 標準算例演示用之前的例子驗證weights [2, 3, 4, 5] values [3, 4, 5, 8] capacity 9 value, mask, count solve_01knapsack_bnb(weights, values, capacity) print(最優(yōu)價值:, value) print(選擇掩碼:, mask) print(物品原始下標:, [i for i, x in enumerate(mask) if x 1]) print(探索節(jié)點數(shù):, count)輸出應(yīng)該是最優(yōu)價值: 13 選擇掩碼: [0, 0, 1, 1] 物品原始下標: [2, 3] 探索節(jié)點數(shù): 12注意掩碼[0, 0, 1, 1]對應(yīng)原始物品 3 和物品 4總重量 4 5 9總價值 5 8 13。整個搜索只訪問 12 個節(jié)點遠小于 31 個節(jié)點的全遍歷量。5. 大規(guī)模實測分支定界、動態(tài)規(guī)劃與回溯法的選型邊界5.1 節(jié)點數(shù)與上界質(zhì)量的關(guān)聯(lián)分支定界的實際表現(xiàn)高度依賴數(shù)據(jù)特征我把它分成兩類典型場景。一類是“強相關(guān)”數(shù)據(jù)。價值與重量強相關(guān)比如價值 2 × 重量 隨機小擾動。這種情況下連續(xù)背包松弛算出的上界和真正整數(shù)最優(yōu)解非常接近剪枝異常迅猛。我實測過 n 200、容量 5000 的強相關(guān)數(shù)據(jù)很多情況下節(jié)點數(shù)只有幾千毫秒級出結(jié)果。另一類是“弱相關(guān)”數(shù)據(jù)。價值和重量基本獨立隨機生成比如重量隨機取 1 到 100價值隨機取 1 到 200。此時連續(xù)背包松弛的上界會明顯虛高剪枝能力大幅下降節(jié)點數(shù)可能膨脹到幾十萬甚至百萬級。n 60、容量 1500 的弱相關(guān)數(shù)據(jù)就要做好它跑好幾秒的心理準備而同樣數(shù)據(jù)用動態(tài)規(guī)劃 O(60×1500) 只要一個 O(nC) 小表就解決了。所以分支定界并不是“更快的最優(yōu)求解器”它是“在某些數(shù)據(jù)分布下特別高效的最優(yōu)求解器”。動手之前先看一下你的數(shù)據(jù)是重相關(guān)還是弱相關(guān)才能判斷要不要選它。5.2 分支定界、動態(tài)規(guī)劃、回溯暴力的適用邊界對照我把三種精確求解方法放在一張表里比較方法時間復(fù)雜度空間復(fù)雜度強項明顯短板回溯暴力最壞 O(2^n)O(n)實現(xiàn)最簡單幾乎不剪枝n 30 就吃力分支定界平均遠小于 2^n最壞 O(2^n)O(n)遞歸棧不依賴容量數(shù)據(jù)強相關(guān)時極快弱相關(guān)數(shù)據(jù)可能退化指數(shù)級動態(tài)規(guī)劃O(nC)O(C) 可滾動穩(wěn)定可預(yù)測小容量場景最優(yōu)容量 C 大時內(nèi)存和耗時爆掉從工程角度我一般這樣選型容量 C 和物品種類 n 都在可接受范圍直接上 DP穩(wěn)定省心。C 特別大、但物品數(shù)據(jù)有明顯密度差異上分支定界。數(shù)據(jù)是弱相關(guān)隨機且 n 很大那就別硬剛精確解考慮啟發(fā)式近似算法更現(xiàn)實。5.3 我踩過的一個遞歸大坑用 Python 寫 DFS 分支定界時有一個隱藏地雷遞歸深度。n 達到 1000 以上時默認遞歸上限很容易爆出RecursionError。解決辦法有兩個一是在腳本開頭設(shè)置sys.setrecursionlimit(10000)二是改用顯式棧。顯式棧還有一個額外好處棧節(jié)點可以動態(tài)排序方便實現(xiàn)后面要說的最佳優(yōu)先搜索。不過代價是代碼復(fù)雜度明顯上升。如果你只是處理幾百個物品遞歸版本足夠沒必要一開始就寫顯式棧。6. 進階玩法Best-First搜索、下界強化與并行注意點6.1 最佳優(yōu)先搜索優(yōu)先處理最有希望的節(jié)點深度優(yōu)先搜索的優(yōu)點是內(nèi)存小但它的“搜索路線”有時很盲目明明某個節(jié)點的上界非常高卻因為遞歸路徑的關(guān)系被排到很晚才處理反而一些上界很低的節(jié)點卻因為出現(xiàn)在遞歸路徑上被優(yōu)先擴展了。Best-First 策略用一個優(yōu)先隊列替代遞歸棧每次取出上界最高的節(jié)點擴展。這樣做的直接好處是算法會非?？斓刈叩揭粭l高質(zhì)量路徑并迅速刷新全局最優(yōu)解。全局最優(yōu)解變緊之后其他節(jié)點的剪枝條件也就更容易滿足。代價是優(yōu)先隊列需要保存大量節(jié)點最壞情況下內(nèi)存會指數(shù)增長。我通常只在解空間特別大、且上界質(zhì)量參差不齊時使用 Best-First。6.2 下界強化起步時用一個好一點的初值很多實現(xiàn)把初始 best_value 設(shè)為 0這其實浪費了第一波剪枝機會。簡單的改進是先跑一遍貪心算法把一個可行解的價值作為初始下界。貪心解雖然不一定最優(yōu)但往往不會太差尤其強相關(guān)數(shù)據(jù)下可能已經(jīng)非常接近最優(yōu)值。這樣搜索一開始就有了一把還算緊的尺子剪枝效率立即提升。更激進的做法是在每個節(jié)點內(nèi)部再做一次局部貪心基于當前已選物品繼續(xù)往后挑選可行解得到一個更精細的下界。但節(jié)點內(nèi)部貪心會增加計算成本對于節(jié)點數(shù)已經(jīng)很少的強相關(guān)數(shù)據(jù)收益不大對于弱相關(guān)數(shù)據(jù)單純加一個啟發(fā)式下界也救不了虛高的上界。所以我的建議是先用全局貪心當初始下界跑一輪看效果再決定要不要加節(jié)點級啟發(fā)式。6.3 并行化的現(xiàn)實考量分支定界天然適合并行根節(jié)點的左右分支彼此獨立可以分給不同工作線程去搜索。工程上需要維護一個全局共享的 best_value任意工作線程發(fā)現(xiàn)更優(yōu)可行解就原子更新其他線程在剪枝判斷時讀取這個全局下界。但并行分支定界有一個典型的坑全局 best 更新可能有延遲某個線程在上界已經(jīng)能剪枝時因為讀到的 best 偏小白白多搜了一整棵子樹。要緩解這個問題可以讓工作線程定期同步全局 best同時在每個子樹搜索開始時重新讀取一次。實際經(jīng)驗是并行只能應(yīng)對“弱相關(guān)大實例”帶來的節(jié)點爆炸而且加速比并不線性很多時候 8 核只跑出 3 到 4 倍提升。如果節(jié)點數(shù)不大并行反而因為線程同步開銷變慢。我建議先把單核版本調(diào)到足夠好再考慮并行。最后分享兩個開發(fā)小技巧。第一實現(xiàn)分支定界時先寫一個完全不帶剪枝的回溯版配合小規(guī)模暴力枚舉或 DP 驗證正確性然后再加 bound 和剪枝一步一確認。第二步專注調(diào)試剪枝條件不然上界函數(shù)出錯時很難定位是“剪錯了最優(yōu)解”還是“搜索路徑本身有 bug”。第二調(diào)優(yōu)時把 node_count 打印出來觀察剪枝前后節(jié)點數(shù)的變化。如果加了剪枝之后節(jié)點數(shù)還和暴力幾乎一樣八成是上界太松或者排序沒生效這時候再回頭檢查上界函數(shù)比盲目加并行要有效得多。