每種物品最多選若干件多重背包若逐件展開會被巨大數(shù)量拖慢。本文沿著面試官的層層追問把數(shù)量拆成一、二、四等二進制組再復用一維零一背包Python 完整代碼覆蓋容量為零、數(shù)量截斷和剩余組并解釋為什么容量循環(huán)必須倒序。倉庫有重量三、價值五的零件一百萬件背包容量只有一百。把一百萬件逐個展開再做零一背包顯然浪費因為最多只能裝三十三件。面試官真正想聽的不是一句“二進制優(yōu)化”而是為什么若干組能表示任意可選數(shù)量、為什么每組只能用一次以及如何先按容量截斷無效庫存。第一問為什么不能復制所有物品將數(shù)量 m 拆成 1、2、4、8 等組最后留下不足下一次冪的余數(shù)。例如 13 拆成 1、2、4、6。每組視為一個重量和價值都乘以組大小的新物品并做零一背包。前三組能組合出 0 到 7加入最后六件組后又能表示 6 到 13與原范圍連接且覆蓋全部合法數(shù)量。組數(shù)從 m 降到 O(log m)。第二問一二四為什么能覆蓋數(shù)量狀態(tài)dp[c]表示容量不超過 c 時的最大價值。處理一個組包(groupWeight,groupValue)時容量從 cap 倒序到 groupWeight更新dp[c]max(dp[c],dp[c-groupWeight]groupValue)。倒序保證右側舊狀態(tài)仍來自處理當前組之前因此每個組最多使用一次。若正序剛更新的 dp 會在同一輪再次被讀取等價于無限使用當前組悄悄變成完全背包。第三問拆完后狀態(tài)怎樣定義樣例容量十物品 A 重三值五最多三件拆成一件組和兩件組物品 B 重四值六最多兩件拆成一件組和一件余數(shù)組。最優(yōu)選擇是兩件 A 加一件 B重量十、價值十六。三件 A 價值十五仍略小兩件 B 加零件 A 會超重。測試直接斷言十六并用一件數(shù)量巨大的重五物品驗證先按capacity//weight截斷后仍只需少數(shù)組包。第四問倒序循環(huán)防住了什么對某種物品的所有組包做零一選擇時組大小的子集和覆蓋 0 到有效數(shù)量的每個整數(shù)因此任何原問題選法都能映射為組包選法每個組最多選一次組合總數(shù)又不會超過原數(shù)量因此反向映射也成立。零一背包轉移枚舉選或不選當前組在處理完全部組后dp 恰好包含所有合法組合的最大價值。第五問數(shù)量很大還有沒有意義若重量或價值為負狀態(tài)語義會改變示例直接拒絕數(shù)量為零則跳過。庫存一百萬但容量很小時先取min(count,capacity//weight)能顯著減少拆分位數(shù)。若業(yè)務要求恰好裝滿需要把不可達狀態(tài)初始化為負無窮只保留 dp[0]0不能沿用“容量不超過”的全零初始化。返回最大價值之外還要恢復方案時可保存選擇路徑或使用二維狀態(tài)。完整可運行代碼defbounded_knapsack(capacity,items):ifcapacity0:raiseValueError(negative capacity)dp[0]*(capacity1)forweight,value,countinitems:ifweight0orvalue0orcount0:raiseValueError(invalid item)countmin(count,capacity//weight)power1whilecount0:takemin(power,count)group_w,group_vweight*take,value*takeforcinrange(capacity,group_w-1,-1):dp[c]max(dp[c],dp[c-group_w]group_v)count-take power1returndp[capacity]if__name____main__:assertbounded_knapsack(10,[(3,5,3),(4,6,2)])16assertbounded_knapsack(0,[(1,9,100)])0assertbounded_knapsack(11,[(5,7,1_000_000)])14assertbounded_knapsack(6,[(2,3,0),(3,4,2)])8print(bounded-knapsack tests passed)把組包列表與狀態(tài)更新對照count先被容量截斷然后每輪取 power 與剩余數(shù)量的較小值所以最后一組可以不是二的冪。容量倒序是整個實現(xiàn)的關鍵不變量。函數(shù)返回 dp[capacity]其含義是容量上限而非必須用滿由于 dp 隨容量不減返回最后一格就是不超過總容量的最大價值。數(shù)量為零不會進入拆分循環(huán)。什么時候改用單調隊列優(yōu)化二進制拆分把數(shù)量維降到對數(shù)級容易復用零一背包也便于恢復選擇。若物品種類很多、容量很大C*Σlog m仍可能太慢。單調隊列優(yōu)化會按重量余數(shù)把容量分組把轉移改寫成固定窗口最大值從而讓每種物品只掃描 O? 狀態(tài)。它更快卻要求對價值表達式做代數(shù)變形窗口邊界和不可達狀態(tài)都更容易出錯。選擇優(yōu)化前應先計算有效數(shù)量。若絕大多數(shù) count 在容量截斷后只有零、一或二二進制拆分的常數(shù)小、實現(xiàn)清楚往往已經足夠。只有當大量物品都能重復很多次且 C 成為真實瓶頸單調隊列才值得引入。可以同時保留樸素小規(guī)模實現(xiàn)作為測試 oracle隨機對照優(yōu)化版本避免性能改造悄悄改變“恰好裝滿”或“至多容量”的語義。背包服務化時還會遇到資源上限與超時。狀態(tài)數(shù)組大小由容量決定不能讓調用方提交任意大整數(shù)直接分配內存。價值和重量的單位應先歸一化以克和毫克混用會把容量放大一千倍。若用最大公約數(shù)縮放所有重量與容量結果保持不變且狀態(tài)數(shù)下降。返回方案時對同價值結果還要約定偏好更輕、件數(shù)更少或字典序更小否則不同實現(xiàn)可能給出不同但同樣最優(yōu)的組合。優(yōu)化版本必須接受樸素裁判在容量零到三十、物品種類一到五的范圍隨機生成數(shù)據用逐種枚舉選取件數(shù)的三維樸素 DP 作為參考。二進制拆分版本與參考值必須完全相同若還實現(xiàn)單調隊列版三者一起對照。測試集合要刻意包含數(shù)量零、重量大于容量、數(shù)量遠大于可容納數(shù)、價值相同和恰好裝滿不可達。性能測試另行使用大容量不能為了跑得快而刪掉正確性裁判。記錄拆分后的組包數(shù)可直接觀察容量截斷是否真正生效。進一步推導練習將容量改為十二為同一種物品設置重量三、價值五、數(shù)量十三先按容量截斷再寫出組包大小。分別用倒序和正序更新一輪找出正序版本如何在同一組上重復獲利。然后把目標改成必須恰好裝滿重新初始化不可達狀態(tài)。預期會看到算法骨架相似但狀態(tài)含義一變初始化和返回條件都必須同步改變。復雜度分析第 i 種物品的有效數(shù)量為 mi拆成 O(log(mi1)) 個組包。每個組包掃描容量 C時間 O(C * Σlog(mi1))空間 O?。先按 C/weight 截斷后mi 不會大于容量可容納件數(shù)。若物品數(shù)量和容量都很大還可研究單調隊列優(yōu)化到 O(NC)但實現(xiàn)與證明更復雜。邊界條件容量零返回零數(shù)量零跳過重量必須為正以避免無限可裝示例要求價值非負有效數(shù)量被容量截斷最后余數(shù)組必須保留。數(shù)值可能超過 32 位時 Python 自動擴展遷移到 Java 或 C 應使用 64 位并估算最大總價值。常見錯誤組大小只取一二四卻忘記剩余量容量正序導致組包可重復選把 count 在拆分前錯誤清零沒有容量截斷導致無意義的大整數(shù)循環(huán)恰好裝滿問題仍以零初始化全部狀態(tài)返回 max(dp) 雖通常相同卻掩蓋了 dp 定義不清。可復制的測試用例運行后預期輸出bounded-knapsack tests passed。四個斷言覆蓋普通組合、零容量、百萬庫存截斷和零數(shù)量物品。進一步可在小容量下用三重循環(huán)的樸素多重背包做對照隨機生成重量、價值與數(shù)量逐例比較結果。上線前復核清單**狀態(tài)**先寫清 dp 是不超過容量還是恰好容量。**拆分**組大小之和必須等于有效數(shù)量余數(shù)組不能丟。**順序**每個組是零一物品所以容量必須倒序。**截斷**數(shù)量超過容量可容納上限的部分永遠無用。**恢復**若要輸出件數(shù)方案需要額外記錄選擇而非只有一維價值。總結二進制拆分的價值是用對數(shù)個零一選擇精確覆蓋零到 m 的所有件數(shù)。理解覆蓋證明和倒序更新后多重背包就不再是另一套陌生模板而是對零一背包輸入規(guī)模的一次壓縮。