9.1 資源分配與背包問題#

本章導言#

第 3 章的線性規劃解決的是「連續資源的最優配置」：原料、工時、預算可以任意細分，單純形法沿著多面體的邊緣走到最優頂點。但管理實務中有一整類問題的資源不可分割：一個投資案要么投、要么不投；一個貨櫃裝得下就裝、裝不下就扔；一個產品經理只能把有限的發版名額給有限的功能。這類「0–1 選擇」問題的原型是背包問題（knapsack problem）——給定背包容量 \(W\) 與 \(n\) 件物品的重量 \(w_i\) 、價值 \(v_i\) ，選一個總重不超過 \(W\) 的子集使總價值最大。背包問題是 NP-hard 的（9.3 節會說明這意味什麼），但其一維形式可用動態規劃在擬多項式時間精確求解，成為管理數學中「結構比暴力更重要」的第一個組合優化示範。

一個被傳說包裝的誕生故事#

關於背包問題與 Dantzig 的軼事流傳甚廣：據說 1930 年代末某次聚會上，有人提出這個問題，Dantzig 當場列式心算得解——事後才發現它是著名的數學難題。無論細節真偽（此軼事版本繁多，細節寧可存疑），可確定的是：1940–50 年代線性規劃誕生後（3.1 節），研究者立刻注意到「把 \(x_j \in [0,1]\) 收緊為 \(x_j \in \{0,1\}\) 」會讓問題性質突變——多面體的整數頂點不再是 \(O(n)\) 可枚舉的，最優解可能遠在「分數解」的對岸。0–1 整數規劃由此成為獨立分支（3.3 節指派問題即其特例），而背包問題是它最簡潔、最常被用作演算法試金石的形式。

動態規劃解法#

設 \(f(j, c)\) 為「只考慮前 \(j\) 件物品、容量剩 \(c\) 時的最大價值」。最優子結構：第 \(j\) 件物品只有裝或不裝兩種可能，

邊界 \(f(0, c) = 0\) 。填表順序 \(j = 1..n\) 、 \(c = 0..W\) ，時間 \(O(nW)\) 、空間 \(O(W)\) （滾動陣列）。注意 \(O(nW)\) 是擬多項式—— \(W\) 以二進位編碼時位元長為 \(\log W\) ，故此演算法不證明問題屬於 P；理論上背包問題是 NP-hard 的。但在 \(W\) 不過分巨大的管理場景（預算以百萬計、物品以百計），DP 表格往往秒級完成，這正是「管理數學不追求漸近極限、追求實例可解」的典型態度。

貪心的教訓：按「價值密度」 \(v_i/w_i\) 由大到小裝入的貪心演算法不保證最優——最後一件物品的「零碎空間」會造成密度排序與實際組合的錯位。DP 之所以正確，是因為它不丟棄「次密度但可拼合」的資訊；這個教訓在 9.2 節網路流（那裡貪心恰好正確）與 3.1 節單純形法（沿邊移動恰好正確）之間形成鮮明對照：同樣是「局部推進」，有沒有最優子結構決定成敗。

例題 9.1.1#

例題 9.1.1：背包容量 \(W = 10\) ，四件物品：

(1) 用貪心（密度序）求解；(2) 用 DP 求最優解並驗證；(3) 比較並解釋差異。

解：

(1) 密度序為 A、C、D、B。依次考慮：裝 A（剩餘容量 \(10-2=8\) ）、裝 C（剩 \(8-4=4\) ）、D 重 5 大於剩餘 4 跳過、B 重 3 小於等於 4 裝入（剩 \(4-3=1\) ）。貪心結果：A+C+B，總重 9，總值 \(10+18+12 = 40\) 。

(2) DP： \(f(j,c)\) 表（節選關鍵列）。最終 \(f(4,10) = 44\) ，最優子集為 A+B+D（重 \(2+3+5=10\) ，值 \(10+12+22=44\) ）。驗算其他候選：A+B+C = 9 重 40 值；C+D = 9 重 40 值；B+D = 8 重 34 值；A+C+D = 11 超重。44 為全局最大。

(3) 貪心得 40，最優 44，差距 10%。原因：密度最高的 A+C 把容量切得七零八落，D（次高密度的「大件」）反而進不去；而 A+B+D 剛好把 10 的容量填滿。貪心只看比值、不看「剩餘空間的結構」，DP 則保留了全部中間狀態。實務啟示：預算分配若按「每元回報率」排名砍預算，常會錯過「整包更划算」的組合——私募基金與廣告預算排程皆有此現象。

背包家族與管理場景#

• 0–1 背包：專案選擇、廣告組合、資本預算（與《會計的數學》第 6 章本量利、第 3 章會計方程連用於投資回收分析）；
• 無界背包：允許重複選同一物品（生產批量的標準化包裝選擇）；
• 多維背包：同時受預算、工時、倉儲多重約束——NP-hard 程度更高，需分支界限或啟發式；
• 集合覆蓋/選址：「每類需求至少被一個設施覆蓋」——背包的對偶形態，與 4.3 節服務網點設計相連。

精確求解 0–1 整數規劃的通用武器是分支界限法（Land–Doig, 1960）：先解 LP 放鬆，若出現分數解就按某變數分兩支搜索，用 LP 最優值作為上界剪枝。背包的 DP 表格本質上就是一種特殊的界限計算。

前因後果與驅動關係#

• 驅動：二戰與戰後的物資配給、港口裝載、軍事空運都需要「不可分割物 + 有限載重」的快速決策；1950 年代運籌學進入企業後，資本預算（一組互斥投資案的選擇）成為背包問題最重要的商業化身。LP（3.1 節）能處理連續量，但董事會看到的是「投或不投」——整數性不是數學偏好，是決策結構。
• 回頭改變實務：DP 與分支界限使百萬級變數的整數規劃可解，直接支撐了航空機位管理、物流裝箱、廣告競價引擎（10.2 節）；「NP-hard」一詞進入管理者的語言，使人理解「有些問題只能求好、不能求最優」——這是啟發式與近似演算法（9.3 節）存在的管理理由。
• 交叉引用：LP 放鬆與對偶見 3.1–3.2 節；指派問題（3.3 節）是背包的雙重約束親戚；背包的貪心失敗對照 9.2 節網路流中貪心的正確性；《金融的數學》第 3 章投資組合的離散化（每支股票最少手數）即多維背包。

練習#

1. \(W=8\) ，物品 \((w,v)\) ： \((3,40),(4,50),(5,60)\) 。分別用貪心密度法與枚舉求最優，驗證 DP 結果為 90。
2. 證明：若所有物品重量均整除 \(W\) ，貪心密度法仍可能非最優（舉 3 件物的例子）。
3. 用滾動陣列把 9.1.1 的 DP 空間從 \(O(nW)\) 降到 \(O(W)\) ，解釋為何第 \(j\) 行只需第 \(j-1\) 行。
4. 把「每專案有收益 \(v_j\) 與佔用預算 \(w_j\) 、總預算 \(W\) 」的資本預算寫成 0–1 整數規劃標準式；若兩個專案互斥（不能同時選），約束如何加？
5. 思考題：廣告競價引擎每秒面對上萬次「出價或不出價」的背包式決策。試論證：在線（不可預知未來）情境下，為何「先到先佔」的貪心反而可能是近似保證最好的策略？（提示：線上演算法的競爭比分析。）

名詞速查表#

• 背包問題：容量約束下選擇 0–1 子集最大化總價值的組合優化問題。
• 0–1 整數規劃：決策變數只能取 0 或 1 的整數規劃。
• 動態規劃：以最優子結構與重疊子問題遞推求解的方法。
• 擬多項式時間：執行時間依賴數值大小 \(W\) 而非其位元長的複雜度。
• 貪心演算法：每步取局部最優、不回溯的構造性演算法。
• 分支界限法：以 LP 放鬆為界、分枝搜索並剪枝的整數規劃通用法。

（本節完）