態(tài)規(guī)劃實(shí)戰(zhàn)：帶附件的多重背包問題解析與C++實(shí)現(xiàn))
1. 項(xiàng)目概述從“多重”到“附件”的背包挑戰(zhàn)在算法競(jìng)賽和實(shí)際的后臺(tái)系統(tǒng)開發(fā)里背包問題是個(gè)繞不開的經(jīng)典模型。很多朋友對(duì)基礎(chǔ)的01背包、完全背包甚至多重背包都有所了解但一旦題目里加上“附件”這個(gè)條件整個(gè)問題的復(fù)雜度就上了一個(gè)臺(tái)階。這不僅僅是物品數(shù)量變多那么簡(jiǎn)單它徹底改變了物品之間的依賴關(guān)系從獨(dú)立的個(gè)體選擇變成了需要組合決策的“套餐”問題。我最初在解決一個(gè)資源分配的系統(tǒng)需求時(shí)就遇到了類似的場(chǎng)景需要為服務(wù)器分配不同類型的計(jì)算資源包主資源每個(gè)資源包又可以綁定幾個(gè)可選的加速插件附件而且主資源和插件都有數(shù)量限制。這不就是活生生的“帶附件的多重背包”嗎網(wǎng)上能找到的教程要么只講多重背包要么只講帶附件的01背包把兩者結(jié)合起來的、講得透徹的實(shí)戰(zhàn)解析并不多。所以我決定結(jié)合自己趟過的坑把這個(gè)問題掰開揉碎了講清楚。這篇文章我會(huì)用C帶你從問題本質(zhì)出發(fā)通過清晰的圖解和逐行注釋的代碼搞定這個(gè)“組合難題”。無論你是正在備戰(zhàn)算法面試還是在開發(fā)中遇到了類似的組合優(yōu)化需求這篇詳解都能給你一套可直接復(fù)用的思路和方案。2. 問題本質(zhì)與核心思路拆解2.1 什么是“帶附件的多重背包”我們先拋開“動(dòng)態(tài)規(guī)劃”這個(gè)術(shù)語(yǔ)用最直白的話描述這個(gè)問題你有一個(gè)容量為V的背包和N種主物品。每種主物品最多可以拿M[i]件這就是“多重”每件主物品占用空間v[i]價(jià)值w[i]。關(guān)鍵來了——部分主物品擁有至多2個(gè)附件物品。附件不能獨(dú)立存在你必須先選擇了它的主物品才能考慮是否選擇對(duì)應(yīng)的附件。每個(gè)附件也有自己的空間占用和價(jià)值并且同樣可能有數(shù)量限制這里我們簡(jiǎn)化討論通常附件數(shù)量限制為1但思路可擴(kuò)展。舉個(gè)例子你要組裝幾臺(tái)電腦主物品每種型號(hào)的電腦有庫(kù)存上限多重。買電腦時(shí)你可以選擇是否同時(shí)購(gòu)買顯示器附件1和機(jī)械鍵盤附件2。你不能單獨(dú)買一個(gè)顯示器而不買電腦。目標(biāo)就是在背包容量?jī)?nèi)讓總價(jià)值最高。這帶來了幾個(gè)核心挑戰(zhàn)依賴關(guān)系附件的選擇依賴于主物品的選擇破壞了物品的獨(dú)立性。組合爆炸對(duì)于一件主物品和其附件選擇方案不再是簡(jiǎn)單的“選”或“不選”而是變成了一個(gè)組合。比如對(duì)于一件有2個(gè)附件的主品所有可能的選擇狀態(tài)有(不選主品)(只選主品)(主品附件1)(主品附件2)(主品附件1附件2)。這5種狀態(tài)在決策時(shí)需要被視為一個(gè)整體來考慮。多重限制主物品本身還有數(shù)量限制這使得我們無法簡(jiǎn)單地將每個(gè)“組合”視為一個(gè)獨(dú)立的新物品進(jìn)行完全背包處理。2.2 思路演化從分組背包到二進(jìn)制優(yōu)化解決這個(gè)問題的核心思路是“化歸”。我們通過兩步將復(fù)雜問題轉(zhuǎn)化為已知模型。第一步處理附件依賴轉(zhuǎn)化為分組背包這是最關(guān)鍵的一步。對(duì)于每一種主物品及其附件我們將其所有有效的選擇方案預(yù)處理出來。什么是有效方案就是所有符合依賴關(guān)系的物品組合。例如主物品A體積v0價(jià)值w0有附件Bv1, w1和附件Cv2, w2。那么它的有效組合有方案0: 空什么都不選體積0價(jià)值0方案1: 只選A體積v0價(jià)值w0方案2: 選A和B體積v0v1價(jià)值w0w1方案3: 選A和C體積v0v2價(jià)值w0w2方案4: 選A、B和C體積v0v1v2價(jià)值w0w1w2注意方案0通常在實(shí)際計(jì)算中不參與轉(zhuǎn)移因?yàn)椴贿x不會(huì)增加價(jià)值。這樣我們就把一種主物品及其附件轉(zhuǎn)化為了一個(gè)“物品組”組內(nèi)有若干個(gè)互斥的“物品”即上述方案但每個(gè)“物品”的體積和價(jià)值是組合后的總值。于是問題變成了有若干個(gè)組每組內(nèi)只能選一個(gè)“物品”即一個(gè)組合方案在容量限制下求最大價(jià)值。這非常接近“分組背包問題”。第二步處理多重限制融入二進(jìn)制優(yōu)化分組背包假設(shè)每組物品只有一個(gè)。但我們?cè)瓎栴}中每種主物品有M[i]件。這意味著上面生成的那個(gè)“物品組”我們可以選多次最多M[i]次但每次選擇都必須是組內(nèi)的一個(gè)完整方案并且多次選擇之間附件也是重復(fù)計(jì)算的即你買兩臺(tái)同型號(hào)電腦每臺(tái)都可以配相同的附件套餐。這聽起來又像“多重背包”了。沒錯(cuò)我們可以這樣理解對(duì)于第i種主物品我們生成了一個(gè)物品組group[i]這個(gè)組里有若干個(gè)方案物品。現(xiàn)在這個(gè)組不是只能選一次而是最多可以選M[i]次。如何處理這個(gè)“多次”經(jīng)典方法是二進(jìn)制優(yōu)化。我們將M[i]件物品的選取次數(shù)拆分成若干個(gè)2的冪次份如1, 2, 4, ..., 2^(k-1), c其中c是剩余的數(shù)。每一份被打包成一個(gè)“新的”物品。但是注意這里打包的不是單個(gè)主物品而是我們前面生成的整個(gè)方案例如主物品i有5件M[i]5。我們將其拆分為1件、2件、2件5122這里用122而不是124是為了演示標(biāo)準(zhǔn)二進(jìn)制是122。那么對(duì)于該主物品對(duì)應(yīng)的物品組里的每一個(gè)方案比如方案“主附1”我們都會(huì)生成3個(gè)新的打包方案打包11倍的“主附1”方案。打包22倍的“主附1”方案體積和價(jià)值都乘2。打包32倍的“主附1”方案。這樣我們通過二進(jìn)制拆分將“第i組物品最多選M[i]次”的限制轉(zhuǎn)化為了對(duì)若干個(gè)“打包后的新物品”做一次01背包問題。而這些“新物品”本身又是從“分組”的概念里來的。最終模型經(jīng)過以上兩步我們得到了一堆“打包后的方案物品”。每個(gè)物品只能選一次01背包且它們之間原本的組別關(guān)系在拆分后已經(jīng)消失因?yàn)槎M(jìn)制拆分后不同次數(shù)的選擇被視為獨(dú)立物品。所以我們最終只需要對(duì)一個(gè)大的物品列表做一次01背包即可。核心心得很多朋友在這里會(huì)暈關(guān)鍵在于理解兩個(gè)層次的轉(zhuǎn)化。第一層是“物品附件”到“組合方案組”分組背包思想第二層是“組合方案組的多重選擇”到“二進(jìn)制拆分后的獨(dú)立物品”多重背包思想。最終都落到了最基礎(chǔ)的01背包上。代碼實(shí)現(xiàn)時(shí)其實(shí)是倒過來的先遍歷物品為每個(gè)主物品生成所有可能方案然后對(duì)這個(gè)方案的集合進(jìn)行二進(jìn)制拆分將拆分后的每個(gè)“包裹”加入待決策的總物品列表。3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與預(yù)處理3.1 如何表示物品與關(guān)系在編碼前清晰的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)能讓邏輯事半功倍。我們需要表示主物品、附件以及它們之間的歸屬關(guān)系。// 定義物品結(jié)構(gòu)體用于存儲(chǔ)所有“最終參與01背包決策的物品” struct Item { int volume; // 組合后的總體積 int value; // 組合后的總價(jià)值 // 注意這個(gè)結(jié)構(gòu)體代表的是經(jīng)過“方案組合”和“二進(jìn)制拆分”后的最終物品 }; // 輸入數(shù)據(jù)通常格式總?cè)萘縑 物品種類數(shù)N主物品數(shù) // 接下來N行每行描述一個(gè)主物品及其可能的附件 // 格式示例v[i], w[i], m[i], a1[i], a2[i] // 其中 a1[i], a2[i] 分別表示附件1和附件2的編號(hào)0表示無附件 // 為了清晰我們通常分開存儲(chǔ)主物品信息和附件信息。 vectorint main_v(N1), main_w(N1), main_m(N1); // 主物品的體積、價(jià)值、數(shù)量上限 vectorint attach_v1(N1), attach_w1(N1); // 附件1的體積、價(jià)值為0表示無 vectorint attach_v2(N1), attach_w2(N1); // 附件2的體積、價(jià)值為0表示無 // 索引從1開始符合日常習(xí)慣在實(shí)際讀入數(shù)據(jù)時(shí)需要根據(jù)附件編號(hào)將附件信息掛載到對(duì)應(yīng)的主物品下。通常題目會(huì)保證附件編號(hào)大于主物品編號(hào)且一個(gè)物品只能是另一個(gè)物品的附件。3.2 方案生成的窮舉與篩選這是預(yù)處理的核心函數(shù)。對(duì)于給定的主物品編號(hào)i我們需要生成其所有有效的選擇方案。vectorItem generateSchemes(int i) { vectorItem schemes; // 方案0: 不選該主物品。在后續(xù)動(dòng)態(tài)規(guī)劃中不選的狀態(tài)是通過dp數(shù)組的繼承實(shí)現(xiàn)的 // 所以我們這里通常不顯式添加一個(gè)體積價(jià)值均為0的方案。 int v0 main_v[i], w0 main_w[i]; int v1 attach_v1[i], w1 attach_w1[i]; int v2 attach_v2[i], w2 attach_w2[i]; // 方案1: 只選主物品 if (v0 V) { // 簡(jiǎn)單體積過濾雖然DP時(shí)也會(huì)判斷這里先過濾掉明顯無效的可以提升效率 schemes.push_back({v0, w0}); } // 方案2: 主物品 附件1 (前提是存在附件1) if (v1 0 (v0 v1) V) { schemes.push_back({v0 v1, w0 w1}); } // 方案3: 主物品 附件2 (前提是存在附件2) if (v2 0 (v0 v2) V) { schemes.push_back({v0 v2, w0 w2}); } // 方案4: 主物品 附件1 附件2 (前提是兩個(gè)附件都存在) if (v1 0 v2 0 (v0 v1 v2) V) { schemes.push_back({v0 v1 v2, w0 w1 w2}); } return schemes; // 返回該主物品的所有有效方案組合 }注意事項(xiàng)為什么只考慮這幾種組合因?yàn)楦郊荒塥?dú)立于主物品存在。所以所有組合都必須包含主物品。理論上如果附件也有多重限制這里的組合數(shù)會(huì)更多但通常題目限制附件數(shù)量為1所以是4種含主物品。另外在生成方案時(shí)就進(jìn)行初步的體積過濾V是一個(gè)有效的剪枝可以避免將完全不可能被放入背包的組合加入后續(xù)計(jì)算。3.3 二進(jìn)制拆分的具體實(shí)現(xiàn)對(duì)于generateSchemes返回的每一個(gè)方案比如一個(gè){v, w}我們都需要根據(jù)該主物品的數(shù)量上限main_m[i]進(jìn)行二進(jìn)制拆分生成多個(gè)“打包物品”。vectorItem allItems; // 用于存儲(chǔ)所有最終參與01背包決策的物品 for (int i 1; i N; i) { vectorItem schemes generateSchemes(i); // 生成當(dāng)前主物品的所有方案 int cnt main_m[i]; // 該主物品的最大數(shù)量 for (const Item scheme : schemes) { // 對(duì)這個(gè)方案進(jìn)行二進(jìn)制拆分 int num cnt; // 當(dāng)前剩余可拆數(shù)量 for (int k 1; k num; k * 2) { int curK min(k, num); // 本次拆出的數(shù)量 // 生成一個(gè)“打包物品”其體積和價(jià)值是原方案的curK倍 allItems.push_back({scheme.volume * curK, scheme.value * curK}); num - curK; } // 二進(jìn)制拆分結(jié)束后num應(yīng)該為0。標(biāo)準(zhǔn)寫法下循環(huán)條件用 k num內(nèi)部用 k * 2 和 num - k 即可。 } }這里有一個(gè)極其關(guān)鍵的細(xì)節(jié)二進(jìn)制拆分是在每個(gè)方案上獨(dú)立進(jìn)行的。比如主物品有5件方案“主附1”被拆成了1份、2份、2份。方案“主附2”同樣被獨(dú)立地拆成1份、2份、2份。這意味著在最終決策時(shí)我們可能會(huì)選擇“1份主附1”和“2份主附2”這對(duì)應(yīng)了實(shí)際場(chǎng)景中買了1臺(tái)帶顯示器A的電腦和2臺(tái)帶鍵盤B的電腦總共3臺(tái)電腦沒有超過5件的限制但組合方式混合了。這是符合題意的因?yàn)轭}目只限制同種主物品的總數(shù)并不要求每次選擇都必須搭配相同的附件。實(shí)操心得這個(gè)細(xì)節(jié)是理解正確性的核心。我們拆分的是“選擇方案”的數(shù)量上限而不是主物品的物理數(shù)量。main_m[i]限制的是主物品i被選擇的總次數(shù)。無論每次選擇搭配什么附件只要主物品i被選中就消耗一次選擇機(jī)會(huì)。我們的二進(jìn)制拆分保證了所有生成的“打包物品”對(duì)應(yīng)的主物品i的選擇次數(shù)之和不會(huì)超過main_m[i]。在代碼中allItems列表里的物品已經(jīng)是獨(dú)立的了它們之間沒有分組約束只有總體積約束。4. 動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)與代碼詳解經(jīng)過預(yù)處理我們得到了allItems列表問題簡(jiǎn)化為標(biāo)準(zhǔn)的01背包。使用一維數(shù)組進(jìn)行空間優(yōu)化是通用且高效的做法。4.1 狀態(tài)定義與轉(zhuǎn)移方程狀態(tài)定義dp[j]表示對(duì)于當(dāng)前已經(jīng)決策過的物品在背包容量恰好為j時(shí)所能獲得的最大價(jià)值。通常使用“恰好”定義可以避免初始化時(shí)的復(fù)雜情況但需要將dp[0]初始化為0其他初始化為負(fù)無窮表示無法達(dá)到。更常用且直觀的是“不超過”定義dp[j]表示容量不超過j時(shí)的最大價(jià)值。我們采用后者。狀態(tài)轉(zhuǎn)移對(duì)于allItems中的每一個(gè)物品item體積v價(jià)值w我們逆序遍歷背包容量j從V到vdp[j] max(dp[j], dp[j - v] w)這是因?yàn)槊總€(gè)物品只能選一次01背包逆序更新保證了在決策當(dāng)前物品時(shí)dp[j - v]引用的狀態(tài)是還未考慮當(dāng)前物品時(shí)的狀態(tài)避免了重復(fù)選取。4.2 完整注釋代碼將上述所有步驟整合得到完整解決方案。#include iostream #include vector #include algorithm using namespace std; struct Item { int vol; // 體積 int val; // 價(jià)值 }; int main() { // 讀取數(shù)據(jù)背包總?cè)萘縑 主物品個(gè)數(shù)N int V, N; cin V N; // 為了清晰使用vector并讓下標(biāo)從1開始 vectorint main_v(N1, 0), main_w(N1, 0), main_m(N1, 0); // 附件信息如果附件編號(hào)為0則表示無附件 vectorint att1_v(N1, 0), att1_w(N1, 0); // 附件1 vectorint att2_v(N1, 0), att2_w(N1, 0); // 附件2 // 假設(shè)輸入格式主物品i的數(shù)據(jù)為 v, w, m, id1, id2 // 其中id1, id2是附件編號(hào)如果為0則無對(duì)應(yīng)附件 // 我們需要先讀入所有主物品信息再根據(jù)附件編號(hào)填充附件信息 // 這里簡(jiǎn)化處理假設(shè)輸入已經(jīng)直接給出了主物品及其附件的體積價(jià)值。 // 更常見的題目輸入是每行描述一個(gè)物品并通過一個(gè)字段指明它是主物品還是附件及其所屬主物品ID。 for (int i 1; i N; i) { int v, w, m, a1, a2; cin v w m a1 a2; main_v[i] v; main_w[i] w; main_m[i] m; // 如果a10則a1是附件所屬主物品的編號(hào)需要把附件信息記錄到主物品下 // 但常見輸入是附件物品單獨(dú)一行用類型字段標(biāo)識(shí)。我們換一種更通用的假設(shè) // 輸入數(shù)據(jù)中物品編號(hào)即行號(hào)。先讀入所有物品的基本信息再處理附件歸屬。 } // 假設(shè)我們通過另一段邏輯已經(jīng)將附件信息正確填充到了att1_v[i], att1_w[i], att2_v[i], att2_w[i]中。 // 例如如果物品i是物品j的附件那么將i的體積價(jià)值記錄到j(luò)的附件槽位里。 vectorItem finalItems; // 最終用于01背包的物品列表 // 遍歷每個(gè)主物品 for (int i 1; i N; i) { if (main_v[i] 0) continue; // 可能該行是附件信息主物品信息無效 // 步驟1: 生成當(dāng)前主物品的所有有效方案 vectorItem schemes; int v0 main_v[i], w0 main_w[i]; int v1 att1_v[i], w1 att1_w[i]; int v2 att2_v[i], w2 att2_w[i]; // 方案1: 僅主物品 schemes.push_back({v0, w0}); // 方案2: 主 附1 if (v1 0) { schemes.push_back({v0 v1, w0 w1}); } // 方案3: 主 附2 if (v2 0) { schemes.push_back({v0 v2, w0 w2}); } // 方案4: 主 附1 附2 if (v1 0 v2 0) { schemes.push_back({v0 v1 v2, w0 w1 w2}); } // 步驟2: 對(duì)每個(gè)方案進(jìn)行二進(jìn)制拆分 int cnt main_m[i]; // 該主物品的可用數(shù)量 for (const Item scheme : schemes) { int num cnt; // 二進(jìn)制拆分 for (int k 1; k num; k 1) { int curK k; // 創(chuàng)建一個(gè)新的打包物品 finalItems.push_back({scheme.vol * curK, scheme.val * curK}); num - curK; } // 處理剩余部分 (標(biāo)準(zhǔn)二進(jìn)制拆分寫法此處num已為0因?yàn)閗循環(huán)到超過num停止) // 更標(biāo)準(zhǔn)的寫法是 // int num cnt; // for (int k 1; k num; k 1) { // finalItems.push_back({scheme.vol * k, scheme.val * k}); // num - k; // } // if (num 0) { // finalItems.push_back({scheme.vol * num, scheme.val * num}); // } } } // 步驟3: 01背包動(dòng)態(tài)規(guī)劃 vectorint dp(V 1, 0); // dp[j] 表示容量不超過j的最大價(jià)值 for (const Item item : finalItems) { // 逆序枚舉容量確保每個(gè)物品只被選用一次 for (int j V; j item.vol; --j) { dp[j] max(dp[j], dp[j - item.vol] item.val); } } // 輸出結(jié)果 cout dp[V] endl; return 0; }4.3 圖解狀態(tài)轉(zhuǎn)移為了更直觀我們考慮一個(gè)超小例子背包容量V10。主物品1體積2價(jià)值3數(shù)量2。無附件。主物品2體積3價(jià)值4數(shù)量1。有附件附件A體積1價(jià)值1。預(yù)處理階段主物品1方案只有{2,3}。數(shù)量2二進(jìn)制拆分為1個(gè){2,3}和1個(gè){4,6}2倍。主物品2方案有僅主{3,4}主附{4,5}。數(shù)量1所以每個(gè)方案拆分為1份。 最終finalItems列表[{2,3}, {4,6}, {3,4}, {4,5}]DP過程一維數(shù)組逆序更新初始化dp[0..10] 0。處理物品{2,3}: 對(duì)j從10到2dp[j]max(dp[j], dp[j-2]3)。更新后dp[2]3,dp[4]6, ...,dp[10]15。處理物品{4,6}: 對(duì)j從10到4例如dp[10]max(15, dp[6]6)。假設(shè)dp[6]在上一步后是9則dp[10]max(15,15)15。處理物品{3,4}: 對(duì)j從10到3更新。處理物品{4,5}: 對(duì)j從10到4更新。最終dp[10]即為答案。通過逆序更新我們確保了每個(gè)“打包物品”只被考慮一次。代碼細(xì)節(jié)提示在二進(jìn)制拆分部分我提供了兩種寫法。第一種是for (int k1; knum; k1)配合num - k并在循環(huán)結(jié)束后判斷num0。第二種是for (int k1; knum; k*2)內(nèi)部用curK min(k, num)。第一種是更經(jīng)典和通用的寫法。務(wù)必理解拆分的目的是用log(n)個(gè)物品的組合來表示選取0~n個(gè)原物品的所有可能性。5. 邊界條件、優(yōu)化與常見問題5.1 初始化與邊界處理dp數(shù)組初始化如果采用“不超過容量j”的定義將dp[0..V]全部初始化為0是安全的。如果采用“恰好裝滿”的定義則需要dp[0]0dp[1..V]-INF負(fù)無窮最后答案是dp[V]。前者更常用且不易出錯(cuò)。無效方案過濾在generateSchemes函數(shù)中生成方案時(shí)判斷組合體積是否V是一個(gè)有效的優(yōu)化可以提前剔除絕對(duì)不可能被放入背包的組合減少后續(xù)二進(jìn)制拆分和DP的物品數(shù)量。主物品數(shù)量為0如果某種主物品的main_m[i]為0則應(yīng)跳過該物品的處理。附件不存在在生成方案時(shí)通過判斷附件體積v1、v2是否大于0來確定附件是否存在是通用的做法。5.2 時(shí)間與空間復(fù)雜度分析假設(shè)有N個(gè)主物品平均每個(gè)主物品有S個(gè)有效方案S4平均數(shù)量限制為M。預(yù)處理階段生成方案O(N*S)二進(jìn)制拆分會(huì)將每種方案拆分為O(logM)個(gè)物品。所以最終參與01背包的物品總數(shù)約為O(N * S * logM)。動(dòng)態(tài)規(guī)劃階段01背包復(fù)雜度為O(物品總數(shù) * V)。因此總時(shí)間復(fù)雜度為O(N * S * logM * V)?？臻g復(fù)雜度主要是一維dp數(shù)組O(V)以及存儲(chǔ)最終物品列表的空間O(N * S * logM)。對(duì)于典型題目N60, V32000, M10這個(gè)復(fù)雜度是完全可接受的。如果V非常大可能需要考慮其他優(yōu)化如單調(diào)隊(duì)列優(yōu)化但結(jié)合了附件依賴后單調(diào)隊(duì)列優(yōu)化會(huì)變得非常復(fù)雜通常筆試面試中不會(huì)考察到那種程度。5.3 常見錯(cuò)誤與調(diào)試技巧錯(cuò)誤忽略了附件不能單獨(dú)選。這是最易犯的錯(cuò)誤。一定要確保生成的每一個(gè)方案都包含了主物品。錯(cuò)誤二進(jìn)制拆分應(yīng)用錯(cuò)誤。記住是對(duì)“每個(gè)方案”進(jìn)行獨(dú)立拆分而不是對(duì)主物品拆分后再組合。如果先對(duì)主物品進(jìn)行二進(jìn)制打包再和附件組合會(huì)漏掉很多混合搭配的情況。錯(cuò)誤dp數(shù)組更新順序。務(wù)必使用逆序從V到item.vol更新一維dp數(shù)組這是01背包空間優(yōu)化的關(guān)鍵。正序更新就變成了完全背包會(huì)導(dǎo)致物品被重復(fù)選取。錯(cuò)誤數(shù)組越界。在DP的內(nèi)層循環(huán)for (int j V; j item.vol; --j)要確保j - item.vol不小于0。調(diào)試技巧打印中間結(jié)果在生成finalItems列表后將其內(nèi)容打印出來檢查每個(gè)物品的體積和價(jià)值是否符合預(yù)期。特別檢查二進(jìn)制拆分后同一主物品的不同方案拆分出的物品體積價(jià)值是否正確。小數(shù)據(jù)測(cè)試構(gòu)造一個(gè)非常小的、可以手動(dòng)計(jì)算的數(shù)據(jù)集比如上面V10的例子一步步跟蹤DP數(shù)組的變化與手動(dòng)計(jì)算結(jié)果比對(duì)。對(duì)比暴力搜索對(duì)于超小數(shù)據(jù)N很小V很小可以寫一個(gè)暴力枚舉所有可能選擇考慮附件依賴和數(shù)量限制的算法與DP結(jié)果對(duì)比確保DP邏輯正確。5.4 問題排查速查表問題現(xiàn)象可能原因檢查點(diǎn)與解決方法結(jié)果比預(yù)期小漏掉了某些高價(jià)值組合1. 檢查generateSchemes函數(shù)是否漏掉了“主附1附2”這種組合2. 檢查二進(jìn)制拆分邏輯是否正確地生成了所有數(shù)量的打包特別是剩余部分if(num0)的處理。3. 檢查輸入數(shù)據(jù)解析附件信息是否正確掛載到了對(duì)應(yīng)的主物品下結(jié)果比預(yù)期大物品被重復(fù)選擇1.最可能DP更新順序錯(cuò)誤將逆序j--寫成了正序j導(dǎo)致完全背包效果。2. 二進(jìn)制拆分邏輯錯(cuò)誤導(dǎo)致拆分出的物品“代表”的數(shù)量總和超過了main_m[i]。運(yùn)行超時(shí)復(fù)雜度太高1. 檢查是否在生成方案時(shí)沒有進(jìn)行體積過濾(V)導(dǎo)致大量無效物品進(jìn)入DP。2. 對(duì)于V很大的情況考慮算法是否已是最優(yōu)題目是否允許此復(fù)雜度。答案錯(cuò)誤小數(shù)據(jù)邊界條件或細(xì)節(jié)錯(cuò)誤1. 使用小數(shù)據(jù)暴力枚舉進(jìn)行對(duì)拍找出第一個(gè)出錯(cuò)的數(shù)據(jù)點(diǎn)。2. 檢查dp數(shù)組初始化值。3. 檢查主物品數(shù)量m[i]為0或1時(shí)的處理。6. 擴(kuò)展與變種思考掌握了這個(gè)標(biāo)準(zhǔn)解法后你可以應(yīng)對(duì)大多數(shù)“帶附件的多重背包”問題。但實(shí)際題目可能會(huì)在此基礎(chǔ)上變化附件也有附件樹形依賴此時(shí)依賴關(guān)系形成一棵樹。解決方案是進(jìn)行樹形DP在樹上進(jìn)行后序遍歷遞歸對(duì)于每個(gè)子樹以一件物品為根計(jì)算在不同容量下選擇該子樹所能獲得的最大價(jià)值這實(shí)際上將問題轉(zhuǎn)化為了一個(gè)分組背包問題子節(jié)點(diǎn)的不同選擇方案構(gòu)成一個(gè)組。這比本題更復(fù)雜但思想一脈相承——處理依賴轉(zhuǎn)化為分組。主物品數(shù)量限制方式變化本題是“最多選M件”。如果是“必須選恰好M件”或“選奇數(shù)件”等需要在狀態(tài)設(shè)計(jì)中增加一維來記錄已選數(shù)量或者結(jié)合費(fèi)用流等其他模型。求方案數(shù)或具體方案如果要求最大價(jià)值對(duì)應(yīng)的方案數(shù)可以將dp數(shù)組改為記錄方案數(shù)轉(zhuǎn)移時(shí)累加。如果要求輸出具體方案則需要記錄狀態(tài)轉(zhuǎn)移路徑通常使用二維數(shù)組或輔助數(shù)組在DP結(jié)束后逆推。最后再分享一個(gè)我自己的調(diào)試習(xí)慣在寫完這類復(fù)雜DP后我會(huì)用一個(gè)簡(jiǎn)單的測(cè)試函數(shù)生成隨機(jī)的小規(guī)模數(shù)據(jù)用暴力算法和DP算法跑一遍對(duì)比結(jié)果。如果連續(xù)多次隨機(jī)測(cè)試都通過代碼的正確性就有了很高的保障。這個(gè)方法在比賽和工程中都非常實(shí)用。 動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：帶附件的多重背包問題解析與C++實(shí)現(xiàn)
1. 項(xiàng)目概述從“多重”到“附件”的背包挑戰(zhàn)在算法競(jìng)賽和實(shí)際的后臺(tái)系統(tǒng)開發(fā)里背包問題是個(gè)繞不開的經(jīng)典模型。很多朋友對(duì)基礎(chǔ)的01背包、完全背包甚至多重背包都有所了解但一旦題目里加上“附件”這個(gè)條件整個(gè)問題的復(fù)雜度就上了一個(gè)臺(tái)階。這不僅僅是物品數(shù)量變多那么簡(jiǎn)單它徹底改變了物品之間的依賴關(guān)系從獨(dú)立的個(gè)體選擇變成了需要組合決策的“套餐”問題。我最初在解決一個(gè)資源分配的系統(tǒng)需求時(shí)就遇到了類似的場(chǎng)景需要為服務(wù)器分配不同類型的計(jì)算資源包主資源每個(gè)資源包又可以綁定幾個(gè)可選的加速插件附件而且主資源和插件都有數(shù)量限制。這不就是活生生的“帶附件的多重背包”嗎網(wǎng)上能找到的教程要么只講多重背包要么只講帶附件的01背包把兩者結(jié)合起來的、講得透徹的實(shí)戰(zhàn)解析并不多。所以我決定結(jié)合自己趟過的坑把這個(gè)問題掰開揉碎了講清楚。這篇文章我會(huì)用C帶你從問題本質(zhì)出發(fā)通過清晰的圖解和逐行注釋的代碼搞定這個(gè)“組合難題”。無論你是正在備戰(zhàn)算法面試還是在開發(fā)中遇到了類似的組合優(yōu)化需求這篇詳解都能給你一套可直接復(fù)用的思路和方案。2. 問題本質(zhì)與核心思路拆解2.1 什么是“帶附件的多重背包”我們先拋開“動(dòng)態(tài)規(guī)劃”這個(gè)術(shù)語(yǔ)用最直白的話描述這個(gè)問題你有一個(gè)容量為V的背包和N種主物品。每種主物品最多可以拿M[i]件這就是“多重”每件主物品占用空間v[i]價(jià)值w[i]。關(guān)鍵來了——部分主物品擁有至多2個(gè)附件物品。附件不能獨(dú)立存在你必須先選擇了它的主物品才能考慮是否選擇對(duì)應(yīng)的附件。每個(gè)附件也有自己的空間占用和價(jià)值并且同樣可能有數(shù)量限制這里我們簡(jiǎn)化討論通常附件數(shù)量限制為1但思路可擴(kuò)展。舉個(gè)例子你要組裝幾臺(tái)電腦主物品每種型號(hào)的電腦有庫(kù)存上限多重。買電腦時(shí)你可以選擇是否同時(shí)購(gòu)買顯示器附件1和機(jī)械鍵盤附件2。你不能單獨(dú)買一個(gè)顯示器而不買電腦。目標(biāo)就是在背包容量?jī)?nèi)讓總價(jià)值最高。這帶來了幾個(gè)核心挑戰(zhàn)依賴關(guān)系附件的選擇依賴于主物品的選擇破壞了物品的獨(dú)立性。組合爆炸對(duì)于一件主物品和其附件選擇方案不再是簡(jiǎn)單的“選”或“不選”而是變成了一個(gè)組合。比如對(duì)于一件有2個(gè)附件的主品所有可能的選擇狀態(tài)有(不選主品)(只選主品)(主品附件1)(主品附件2)(主品附件1附件2)。這5種狀態(tài)在決策時(shí)需要被視為一個(gè)整體來考慮。多重限制主物品本身還有數(shù)量限制這使得我們無法簡(jiǎn)單地將每個(gè)“組合”視為一個(gè)獨(dú)立的新物品進(jìn)行完全背包處理。2.2 思路演化從分組背包到二進(jìn)制優(yōu)化解決這個(gè)問題的核心思路是“化歸”。我們通過兩步將復(fù)雜問題轉(zhuǎn)化為已知模型。第一步處理附件依賴轉(zhuǎn)化為分組背包這是最關(guān)鍵的一步。對(duì)于每一種主物品及其附件我們將其所有有效的選擇方案預(yù)處理出來。什么是有效方案就是所有符合依賴關(guān)系的物品組合。例如主物品A體積v0價(jià)值w0有附件Bv1, w1和附件Cv2, w2。那么它的有效組合有方案0: 空什么都不選體積0價(jià)值0方案1: 只選A體積v0價(jià)值w0方案2: 選A和B體積v0v1價(jià)值w0w1方案3: 選A和C體積v0v2價(jià)值w0w2方案4: 選A、B和C體積v0v1v2價(jià)值w0w1w2注意方案0通常在實(shí)際計(jì)算中不參與轉(zhuǎn)移因?yàn)椴贿x不會(huì)增加價(jià)值。這樣我們就把一種主物品及其附件轉(zhuǎn)化為了一個(gè)“物品組”組內(nèi)有若干個(gè)互斥的“物品”即上述方案但每個(gè)“物品”的體積和價(jià)值是組合后的總值。于是問題變成了有若干個(gè)組每組內(nèi)只能選一個(gè)“物品”即一個(gè)組合方案在容量限制下求最大價(jià)值。這非常接近“分組背包問題”。第二步處理多重限制融入二進(jìn)制優(yōu)化分組背包假設(shè)每組物品只有一個(gè)。但我們?cè)瓎栴}中每種主物品有M[i]件。這意味著上面生成的那個(gè)“物品組”我們可以選多次最多M[i]次但每次選擇都必須是組內(nèi)的一個(gè)完整方案并且多次選擇之間附件也是重復(fù)計(jì)算的即你買兩臺(tái)同型號(hào)電腦每臺(tái)都可以配相同的附件套餐。這聽起來又像“多重背包”了。沒錯(cuò)我們可以這樣理解對(duì)于第i種主物品我們生成了一個(gè)物品組group[i]這個(gè)組里有若干個(gè)方案物品。現(xiàn)在這個(gè)組不是只能選一次而是最多可以選M[i]次。如何處理這個(gè)“多次”經(jīng)典方法是二進(jìn)制優(yōu)化。我們將M[i]件物品的選取次數(shù)拆分成若干個(gè)2的冪次份如1, 2, 4, ..., 2^(k-1), c其中c是剩余的數(shù)。每一份被打包成一個(gè)“新的”物品。但是注意這里打包的不是單個(gè)主物品而是我們前面生成的整個(gè)方案例如主物品i有5件M[i]5。我們將其拆分為1件、2件、2件5122這里用122而不是124是為了演示標(biāo)準(zhǔn)二進(jìn)制是122。那么對(duì)于該主物品對(duì)應(yīng)的物品組里的每一個(gè)方案比如方案“主附1”我們都會(huì)生成3個(gè)新的打包方案打包11倍的“主附1”方案。打包22倍的“主附1”方案體積和價(jià)值都乘2。打包32倍的“主附1”方案。這樣我們通過二進(jìn)制拆分將“第i組物品最多選M[i]次”的限制轉(zhuǎn)化為了對(duì)若干個(gè)“打包后的新物品”做一次01背包問題。而這些“新物品”本身又是從“分組”的概念里來的。最終模型經(jīng)過以上兩步我們得到了一堆“打包后的方案物品”。每個(gè)物品只能選一次01背包且它們之間原本的組別關(guān)系在拆分后已經(jīng)消失因?yàn)槎M(jìn)制拆分后不同次數(shù)的選擇被視為獨(dú)立物品。所以我們最終只需要對(duì)一個(gè)大的物品列表做一次01背包即可。核心心得很多朋友在這里會(huì)暈關(guān)鍵在于理解兩個(gè)層次的轉(zhuǎn)化。第一層是“物品附件”到“組合方案組”分組背包思想第二層是“組合方案組的多重選擇”到“二進(jìn)制拆分后的獨(dú)立物品”多重背包思想。最終都落到了最基礎(chǔ)的01背包上。代碼實(shí)現(xiàn)時(shí)其實(shí)是倒過來的先遍歷物品為每個(gè)主物品生成所有可能方案然后對(duì)這個(gè)方案的集合進(jìn)行二進(jìn)制拆分將拆分后的每個(gè)“包裹”加入待決策的總物品列表。3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與預(yù)處理3.1 如何表示物品與關(guān)系在編碼前清晰的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)能讓邏輯事半功倍。我們需要表示主物品、附件以及它們之間的歸屬關(guān)系。// 定義物品結(jié)構(gòu)體用于存儲(chǔ)所有“最終參與01背包決策的物品” struct Item { int volume; // 組合后的總體積 int value; // 組合后的總價(jià)值 // 注意這個(gè)結(jié)構(gòu)體代表的是經(jīng)過“方案組合”和“二進(jìn)制拆分”后的最終物品 }; // 輸入數(shù)據(jù)通常格式總?cè)萘縑 物品種類數(shù)N主物品數(shù) // 接下來N行每行描述一個(gè)主物品及其可能的附件 // 格式示例v[i], w[i], m[i], a1[i], a2[i] // 其中 a1[i], a2[i] 分別表示附件1和附件2的編號(hào)0表示無附件 // 為了清晰我們通常分開存儲(chǔ)主物品信息和附件信息。 vectorint main_v(N1), main_w(N1), main_m(N1); // 主物品的體積、價(jià)值、數(shù)量上限 vectorint attach_v1(N1), attach_w1(N1); // 附件1的體積、價(jià)值為0表示無 vectorint attach_v2(N1), attach_w2(N1); // 附件2的體積、價(jià)值為0表示無 // 索引從1開始符合日常習(xí)慣在實(shí)際讀入數(shù)據(jù)時(shí)需要根據(jù)附件編號(hào)將附件信息掛載到對(duì)應(yīng)的主物品下。通常題目會(huì)保證附件編號(hào)大于主物品編號(hào)且一個(gè)物品只能是另一個(gè)物品的附件。3.2 方案生成的窮舉與篩選這是預(yù)處理的核心函數(shù)。對(duì)于給定的主物品編號(hào)i我們需要生成其所有有效的選擇方案。vectorItem generateSchemes(int i) { vectorItem schemes; // 方案0: 不選該主物品。在后續(xù)動(dòng)態(tài)規(guī)劃中不選的狀態(tài)是通過dp數(shù)組的繼承實(shí)現(xiàn)的 // 所以我們這里通常不顯式添加一個(gè)體積價(jià)值均為0的方案。 int v0 main_v[i], w0 main_w[i]; int v1 attach_v1[i], w1 attach_w1[i]; int v2 attach_v2[i], w2 attach_w2[i]; // 方案1: 只選主物品 if (v0 V) { // 簡(jiǎn)單體積過濾雖然DP時(shí)也會(huì)判斷這里先過濾掉明顯無效的可以提升效率 schemes.push_back({v0, w0}); } // 方案2: 主物品 附件1 (前提是存在附件1) if (v1 0 (v0 v1) V) { schemes.push_back({v0 v1, w0 w1}); } // 方案3: 主物品 附件2 (前提是存在附件2) if (v2 0 (v0 v2) V) { schemes.push_back({v0 v2, w0 w2}); } // 方案4: 主物品 附件1 附件2 (前提是兩個(gè)附件都存在) if (v1 0 v2 0 (v0 v1 v2) V) { schemes.push_back({v0 v1 v2, w0 w1 w2}); } return schemes; // 返回該主物品的所有有效方案組合 }注意事項(xiàng)為什么只考慮這幾種組合因?yàn)楦郊荒塥?dú)立于主物品存在。所以所有組合都必須包含主物品。理論上如果附件也有多重限制這里的組合數(shù)會(huì)更多但通常題目限制附件數(shù)量為1所以是4種含主物品。另外在生成方案時(shí)就進(jìn)行初步的體積過濾V是一個(gè)有效的剪枝可以避免將完全不可能被放入背包的組合加入后續(xù)計(jì)算。3.3 二進(jìn)制拆分的具體實(shí)現(xiàn)對(duì)于generateSchemes返回的每一個(gè)方案比如一個(gè){v, w}我們都需要根據(jù)該主物品的數(shù)量上限main_m[i]進(jìn)行二進(jìn)制拆分生成多個(gè)“打包物品”。vectorItem allItems; // 用于存儲(chǔ)所有最終參與01背包決策的物品 for (int i 1; i N; i) { vectorItem schemes generateSchemes(i); // 生成當(dāng)前主物品的所有方案 int cnt main_m[i]; // 該主物品的最大數(shù)量 for (const Item scheme : schemes) { // 對(duì)這個(gè)方案進(jìn)行二進(jìn)制拆分 int num cnt; // 當(dāng)前剩余可拆數(shù)量 for (int k 1; k num; k * 2) { int curK min(k, num); // 本次拆出的數(shù)量 // 生成一個(gè)“打包物品”其體積和價(jià)值是原方案的curK倍 allItems.push_back({scheme.volume * curK, scheme.value * curK}); num - curK; } // 二進(jìn)制拆分結(jié)束后num應(yīng)該為0。標(biāo)準(zhǔn)寫法下循環(huán)條件用 k num內(nèi)部用 k * 2 和 num - k 即可。 } }這里有一個(gè)極其關(guān)鍵的細(xì)節(jié)二進(jìn)制拆分是在每個(gè)方案上獨(dú)立進(jìn)行的。比如主物品有5件方案“主附1”被拆成了1份、2份、2份。方案“主附2”同樣被獨(dú)立地拆成1份、2份、2份。這意味著在最終決策時(shí)我們可能會(huì)選擇“1份主附1”和“2份主附2”這對(duì)應(yīng)了實(shí)際場(chǎng)景中買了1臺(tái)帶顯示器A的電腦和2臺(tái)帶鍵盤B的電腦總共3臺(tái)電腦沒有超過5件的限制但組合方式混合了。這是符合題意的因?yàn)轭}目只限制同種主物品的總數(shù)并不要求每次選擇都必須搭配相同的附件。實(shí)操心得這個(gè)細(xì)節(jié)是理解正確性的核心。我們拆分的是“選擇方案”的數(shù)量上限而不是主物品的物理數(shù)量。main_m[i]限制的是主物品i被選擇的總次數(shù)。無論每次選擇搭配什么附件只要主物品i被選中就消耗一次選擇機(jī)會(huì)。我們的二進(jìn)制拆分保證了所有生成的“打包物品”對(duì)應(yīng)的主物品i的選擇次數(shù)之和不會(huì)超過main_m[i]。在代碼中allItems列表里的物品已經(jīng)是獨(dú)立的了它們之間沒有分組約束只有總體積約束。4. 動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)與代碼詳解經(jīng)過預(yù)處理我們得到了allItems列表問題簡(jiǎn)化為標(biāo)準(zhǔn)的01背包。使用一維數(shù)組進(jìn)行空間優(yōu)化是通用且高效的做法。4.1 狀態(tài)定義與轉(zhuǎn)移方程狀態(tài)定義dp[j]表示對(duì)于當(dāng)前已經(jīng)決策過的物品在背包容量恰好為j時(shí)所能獲得的最大價(jià)值。通常使用“恰好”定義可以避免初始化時(shí)的復(fù)雜情況但需要將dp[0]初始化為0其他初始化為負(fù)無窮表示無法達(dá)到。更常用且直觀的是“不超過”定義dp[j]表示容量不超過j時(shí)的最大價(jià)值。我們采用后者。狀態(tài)轉(zhuǎn)移對(duì)于allItems中的每一個(gè)物品item體積v價(jià)值w我們逆序遍歷背包容量j從V到vdp[j] max(dp[j], dp[j - v] w)這是因?yàn)槊總€(gè)物品只能選一次01背包逆序更新保證了在決策當(dāng)前物品時(shí)dp[j - v]引用的狀態(tài)是還未考慮當(dāng)前物品時(shí)的狀態(tài)避免了重復(fù)選取。4.2 完整注釋代碼將上述所有步驟整合得到完整解決方案。#include iostream #include vector #include algorithm using namespace std; struct Item { int vol; // 體積 int val; // 價(jià)值 }; int main() { // 讀取數(shù)據(jù)背包總?cè)萘縑 主物品個(gè)數(shù)N int V, N; cin V N; // 為了清晰使用vector并讓下標(biāo)從1開始 vectorint main_v(N1, 0), main_w(N1, 0), main_m(N1, 0); // 附件信息如果附件編號(hào)為0則表示無附件 vectorint att1_v(N1, 0), att1_w(N1, 0); // 附件1 vectorint att2_v(N1, 0), att2_w(N1, 0); // 附件2 // 假設(shè)輸入格式主物品i的數(shù)據(jù)為 v, w, m, id1, id2 // 其中id1, id2是附件編號(hào)如果為0則無對(duì)應(yīng)附件 // 我們需要先讀入所有主物品信息再根據(jù)附件編號(hào)填充附件信息 // 這里簡(jiǎn)化處理假設(shè)輸入已經(jīng)直接給出了主物品及其附件的體積價(jià)值。 // 更常見的題目輸入是每行描述一個(gè)物品并通過一個(gè)字段指明它是主物品還是附件及其所屬主物品ID。 for (int i 1; i N; i) { int v, w, m, a1, a2; cin v w m a1 a2; main_v[i] v; main_w[i] w; main_m[i] m; // 如果a10則a1是附件所屬主物品的編號(hào)需要把附件信息記錄到主物品下 // 但常見輸入是附件物品單獨(dú)一行用類型字段標(biāo)識(shí)。我們換一種更通用的假設(shè) // 輸入數(shù)據(jù)中物品編號(hào)即行號(hào)。先讀入所有物品的基本信息再處理附件歸屬。 } // 假設(shè)我們通過另一段邏輯已經(jīng)將附件信息正確填充到了att1_v[i], att1_w[i], att2_v[i], att2_w[i]中。 // 例如如果物品i是物品j的附件那么將i的體積價(jià)值記錄到j(luò)的附件槽位里。 vectorItem finalItems; // 最終用于01背包的物品列表 // 遍歷每個(gè)主物品 for (int i 1; i N; i) { if (main_v[i] 0) continue; // 可能該行是附件信息主物品信息無效 // 步驟1: 生成當(dāng)前主物品的所有有效方案 vectorItem schemes; int v0 main_v[i], w0 main_w[i]; int v1 att1_v[i], w1 att1_w[i]; int v2 att2_v[i], w2 att2_w[i]; // 方案1: 僅主物品 schemes.push_back({v0, w0}); // 方案2: 主 附1 if (v1 0) { schemes.push_back({v0 v1, w0 w1}); } // 方案3: 主 附2 if (v2 0) { schemes.push_back({v0 v2, w0 w2}); } // 方案4: 主 附1 附2 if (v1 0 v2 0) { schemes.push_back({v0 v1 v2, w0 w1 w2}); } // 步驟2: 對(duì)每個(gè)方案進(jìn)行二進(jìn)制拆分 int cnt main_m[i]; // 該主物品的可用數(shù)量 for (const Item scheme : schemes) { int num cnt; // 二進(jìn)制拆分 for (int k 1; k num; k 1) { int curK k; // 創(chuàng)建一個(gè)新的打包物品 finalItems.push_back({scheme.vol * curK, scheme.val * curK}); num - curK; } // 處理剩余部分 (標(biāo)準(zhǔn)二進(jìn)制拆分寫法此處num已為0因?yàn)閗循環(huán)到超過num停止) // 更標(biāo)準(zhǔn)的寫法是 // int num cnt; // for (int k 1; k num; k 1) { // finalItems.push_back({scheme.vol * k, scheme.val * k}); // num - k; // } // if (num 0) { // finalItems.push_back({scheme.vol * num, scheme.val * num}); // } } } // 步驟3: 01背包動(dòng)態(tài)規(guī)劃 vectorint dp(V 1, 0); // dp[j] 表示容量不超過j的最大價(jià)值 for (const Item item : finalItems) { // 逆序枚舉容量確保每個(gè)物品只被選用一次 for (int j V; j item.vol; --j) { dp[j] max(dp[j], dp[j - item.vol] item.val); } } // 輸出結(jié)果 cout dp[V] endl; return 0; }4.3 圖解狀態(tài)轉(zhuǎn)移為了更直觀我們考慮一個(gè)超小例子背包容量V10。主物品1體積2價(jià)值3數(shù)量2。無附件。主物品2體積3價(jià)值4數(shù)量1。有附件附件A體積1價(jià)值1。預(yù)處理階段主物品1方案只有{2,3}。數(shù)量2二進(jìn)制拆分為1個(gè){2,3}和1個(gè){4,6}2倍。主物品2方案有僅主{3,4}主附{4,5}。數(shù)量1所以每個(gè)方案拆分為1份。 最終finalItems列表[{2,3}, {4,6}, {3,4}, {4,5}]DP過程一維數(shù)組逆序更新初始化dp[0..10] 0。處理物品{2,3}: 對(duì)j從10到2dp[j]max(dp[j], dp[j-2]3)。更新后dp[2]3,dp[4]6, ...,dp[10]15。處理物品{4,6}: 對(duì)j從10到4例如dp[10]max(15, dp[6]6)。假設(shè)dp[6]在上一步后是9則dp[10]max(15,15)15。處理物品{3,4}: 對(duì)j從10到3更新。處理物品{4,5}: 對(duì)j從10到4更新。最終dp[10]即為答案。通過逆序更新我們確保了每個(gè)“打包物品”只被考慮一次。代碼細(xì)節(jié)提示在二進(jìn)制拆分部分我提供了兩種寫法。第一種是for (int k1; knum; k1)配合num - k并在循環(huán)結(jié)束后判斷num0。第二種是for (int k1; knum; k*2)內(nèi)部用curK min(k, num)。第一種是更經(jīng)典和通用的寫法。務(wù)必理解拆分的目的是用log(n)個(gè)物品的組合來表示選取0~n個(gè)原物品的所有可能性。5. 邊界條件、優(yōu)化與常見問題5.1 初始化與邊界處理dp數(shù)組初始化如果采用“不超過容量j”的定義將dp[0..V]全部初始化為0是安全的。如果采用“恰好裝滿”的定義則需要dp[0]0dp[1..V]-INF負(fù)無窮最后答案是dp[V]。前者更常用且不易出錯(cuò)。無效方案過濾在generateSchemes函數(shù)中生成方案時(shí)判斷組合體積是否V是一個(gè)有效的優(yōu)化可以提前剔除絕對(duì)不可能被放入背包的組合減少后續(xù)二進(jìn)制拆分和DP的物品數(shù)量。主物品數(shù)量為0如果某種主物品的main_m[i]為0則應(yīng)跳過該物品的處理。附件不存在在生成方案時(shí)通過判斷附件體積v1、v2是否大于0來確定附件是否存在是通用的做法。5.2 時(shí)間與空間復(fù)雜度分析假設(shè)有N個(gè)主物品平均每個(gè)主物品有S個(gè)有效方案S4平均數(shù)量限制為M。預(yù)處理階段生成方案O(N*S)二進(jìn)制拆分會(huì)將每種方案拆分為O(logM)個(gè)物品。所以最終參與01背包的物品總數(shù)約為O(N * S * logM)。動(dòng)態(tài)規(guī)劃階段01背包復(fù)雜度為O(物品總數(shù) * V)。因此總時(shí)間復(fù)雜度為O(N * S * logM * V)?？臻g復(fù)雜度主要是一維dp數(shù)組O(V)以及存儲(chǔ)最終物品列表的空間O(N * S * logM)。對(duì)于典型題目N60, V32000, M10這個(gè)復(fù)雜度是完全可接受的。如果V非常大可能需要考慮其他優(yōu)化如單調(diào)隊(duì)列優(yōu)化但結(jié)合了附件依賴后單調(diào)隊(duì)列優(yōu)化會(huì)變得非常復(fù)雜通常筆試面試中不會(huì)考察到那種程度。5.3 常見錯(cuò)誤與調(diào)試技巧錯(cuò)誤忽略了附件不能單獨(dú)選。這是最易犯的錯(cuò)誤。一定要確保生成的每一個(gè)方案都包含了主物品。錯(cuò)誤二進(jìn)制拆分應(yīng)用錯(cuò)誤。記住是對(duì)“每個(gè)方案”進(jìn)行獨(dú)立拆分而不是對(duì)主物品拆分后再組合。如果先對(duì)主物品進(jìn)行二進(jìn)制打包再和附件組合會(huì)漏掉很多混合搭配的情況。錯(cuò)誤dp數(shù)組更新順序。務(wù)必使用逆序從V到item.vol更新一維dp數(shù)組這是01背包空間優(yōu)化的關(guān)鍵。正序更新就變成了完全背包會(huì)導(dǎo)致物品被重復(fù)選取。錯(cuò)誤數(shù)組越界。在DP的內(nèi)層循環(huán)for (int j V; j item.vol; --j)要確保j - item.vol不小于0。調(diào)試技巧打印中間結(jié)果在生成finalItems列表后將其內(nèi)容打印出來檢查每個(gè)物品的體積和價(jià)值是否符合預(yù)期。特別檢查二進(jìn)制拆分后同一主物品的不同方案拆分出的物品體積價(jià)值是否正確。小數(shù)據(jù)測(cè)試構(gòu)造一個(gè)非常小的、可以手動(dòng)計(jì)算的數(shù)據(jù)集比如上面V10的例子一步步跟蹤DP數(shù)組的變化與手動(dòng)計(jì)算結(jié)果比對(duì)。對(duì)比暴力搜索對(duì)于超小數(shù)據(jù)N很小V很小可以寫一個(gè)暴力枚舉所有可能選擇考慮附件依賴和數(shù)量限制的算法與DP結(jié)果對(duì)比確保DP邏輯正確。5.4 問題排查速查表問題現(xiàn)象可能原因檢查點(diǎn)與解決方法結(jié)果比預(yù)期小漏掉了某些高價(jià)值組合1. 檢查generateSchemes函數(shù)是否漏掉了“主附1附2”這種組合2. 檢查二進(jìn)制拆分邏輯是否正確地生成了所有數(shù)量的打包特別是剩余部分if(num0)的處理。3. 檢查輸入數(shù)據(jù)解析附件信息是否正確掛載到了對(duì)應(yīng)的主物品下結(jié)果比預(yù)期大物品被重復(fù)選擇1.最可能DP更新順序錯(cuò)誤將逆序j--寫成了正序j導(dǎo)致完全背包效果。2. 二進(jìn)制拆分邏輯錯(cuò)誤導(dǎo)致拆分出的物品“代表”的數(shù)量總和超過了main_m[i]。運(yùn)行超時(shí)復(fù)雜度太高1. 檢查是否在生成方案時(shí)沒有進(jìn)行體積過濾(V)導(dǎo)致大量無效物品進(jìn)入DP。2. 對(duì)于V很大的情況考慮算法是否已是最優(yōu)題目是否允許此復(fù)雜度。答案錯(cuò)誤小數(shù)據(jù)邊界條件或細(xì)節(jié)錯(cuò)誤1. 使用小數(shù)據(jù)暴力枚舉進(jìn)行對(duì)拍找出第一個(gè)出錯(cuò)的數(shù)據(jù)點(diǎn)。2. 檢查dp數(shù)組初始化值。3. 檢查主物品數(shù)量m[i]為0或1時(shí)的處理。6. 擴(kuò)展與變種思考掌握了這個(gè)標(biāo)準(zhǔn)解法后你可以應(yīng)對(duì)大多數(shù)“帶附件的多重背包”問題。但實(shí)際題目可能會(huì)在此基礎(chǔ)上變化附件也有附件樹形依賴此時(shí)依賴關(guān)系形成一棵樹。解決方案是進(jìn)行樹形DP在樹上進(jìn)行后序遍歷遞歸對(duì)于每個(gè)子樹以一件物品為根計(jì)算在不同容量下選擇該子樹所能獲得的最大價(jià)值這實(shí)際上將問題轉(zhuǎn)化為了一個(gè)分組背包問題子節(jié)點(diǎn)的不同選擇方案構(gòu)成一個(gè)組。這比本題更復(fù)雜但思想一脈相承——處理依賴轉(zhuǎn)化為分組。主物品數(shù)量限制方式變化本題是“最多選M件”。如果是“必須選恰好M件”或“選奇數(shù)件”等需要在狀態(tài)設(shè)計(jì)中增加一維來記錄已選數(shù)量或者結(jié)合費(fèi)用流等其他模型。求方案數(shù)或具體方案如果要求最大價(jià)值對(duì)應(yīng)的方案數(shù)可以將dp數(shù)組改為記錄方案數(shù)轉(zhuǎn)移時(shí)累加。如果要求輸出具體方案則需要記錄狀態(tài)轉(zhuǎn)移路徑通常使用二維數(shù)組或輔助數(shù)組在DP結(jié)束后逆推。最后再分享一個(gè)我自己的調(diào)試習(xí)慣在寫完這類復(fù)雜DP后我會(huì)用一個(gè)簡(jiǎn)單的測(cè)試函數(shù)生成隨機(jī)的小規(guī)模數(shù)據(jù)用暴力算法和DP算法跑一遍對(duì)比結(jié)果。如果連續(xù)多次隨機(jī)測(cè)試都通過代碼的正確性就有了很高的保障。這個(gè)方法在比賽和工程中都非常實(shí)用。