研究所考試

在經典的組合優化問題中，0/1 背包問題（0/1 Knapsack Problem）是一個廣為研究的 NP-complete 問題。問題的基本設定為：給定 n 個物品，每個物品具有一個重量 w_i 與價值 v_i，以及一個背包，其總容量為 C。目標是在不超過容量限制的前提下，選擇部分物品放入背包，以最大化所獲得的總價值。所謂「0/1」指的是每個物品只能被完全選擇或完全不選擇（即 x_i∈0,1），不能部分切割。由於其整數決策的特性，此問題通常需透過動態規劃、分支界限法、整數規劃等方式來求解，而無法在多項式時間內保證得到最優解。

相較之下，分數背包問題（Fractional Knapsack Problem）則放寬了上述條件，允許每個物品可被拆分成任意比例，對應地獲得部分價值。也就是說，若某個物品的完整重量無法容納於剩餘容量中，仍可選擇其一部分加入背包。這樣的設定轉化為一個線性規劃問題，可以透過貪婪策略以多項式時間內高效解決。具體而言，只需依據價值密度（即 v_i/w_i ）對所有物品排序，然後依序裝入背包，直到容量耗盡為止。由於分數背包問題具有凸性與連續性，其解可作為 0/1 背包問題中的上界估算，常用於設計剪枝策略與近似演算法。

總結而言，0/1 背包與分數背包的主要差異在於決策空間的離散性與連續性。前者的解空間為離散整數集合，問題較難解析，卻更貼近現實中物品不可分割的限制；後者則具備連續性，易於計算與分析，常被用於作為啟發式方法中的上界估算工具。然而，在許多實際應用場景中，單一背包並不足以反映問題的複雜性，例如多輛運輸車輛、多台伺服器或多個人力資源池等。在這類情境下，資源需分配至多個容器，每個容器均有獨立容量限制，此時傳統背包模型便需擴展為多重背包問題（Multiple Knapsack Problem, MKP）。MKP 可視為 0/1 背包問題的自然推廣，其整體結構與解法特性雖有相似之處，但因多個背包間的交互分配決策，問題難度亦隨之提升，成為許多資源分配與作業規劃問題中的核心模型之一。

問題定義給定：

• n 個物品，第 i 個物品有重量 w_i 和價值 v_i。
• m 個背包，第 j 個背包有容量 C_j。

目標：從這些物品中選擇一部分，分配給 m 個背包（每個物品只能放入一個背包，且只能放一次），使得：

• 不超過任何背包的容量限制。
• 總價值最大化（即所選物品的價值總和最大）。

數學模型

解法概觀

由於多重背包問題屬於 NP-hard 問題，其求解策略可大致分為兩類：精確解法與近似或啟發式解法。精確解法如分支界限法（Branch and Bound）、整數線性規劃（Integer Linear Programming, ILP）等，能保證找到最優解，適用於問題規模較小或中等的情境。然而，隨著物品數與背包數增加，這些方法的計算成本將迅速上升。為因應大規模應用需求，許多研究提出了貪婪演算法、模擬退火、遺傳演算法等啟發式與近似解法，雖無法保證找到全域最優解，卻能在合理時間內取得品質良好的可行解。此外，也有部分方法結合貪婪初解與局部搜尋策略，或利用分數背包問題所計算的上界進行剪枝，有效提升搜尋效率。不同解法在時間效率與解品質間取捨，各自適用於不同應用場景。以下會從最佳解與近似解中各自挑選其中一種解法作說明，讓讀者可以從問題規模選擇相對應的解法。

分支界限法核心概念 分支界限法是一種搜尋演算法，它建立一棵決策樹來系統地探索所有可能的解。每個節點表示目前的部分解（partial assignment），演算法會：

• 在每個節點做出決策（分支）
• 計算該節點可能達到的最大價值（上界）
• 若無法超越目前最佳解，就剪枝（不再往下展開）

搜尋樹設計方式（Branching） 假設我們依照物品順序決策，對每個物品，我們有 (m+1) 種選擇：

• 將物品放入背包 1、2、…、m 中（前提是容量夠）
• 或是 不選擇該物品（跳過）

每個節點需記錄以下資訊：

• 已放入背包的物品清單（或一個物品對背包的映射）
• 每個背包目前的剩餘容量
• 當前總價值
• 下一個要決策的物品編號 k

上界估算（Bounding） 我們對每個節點估算其最大可能總價值（upper bound），來決定是否值得繼續展開。
假設：

• 接下來還有一些物品尚未分配（從 k 到 n）
• 我們可以用「價值密度 v_i/w_i 」排序剩餘物品
• 然後以背包剩餘空間為上限，嘗試放入物品或分數物品（fractional）

這其實就是 0-1 背包問題中的分數背包（Fractional Knapsack）作為上界。這樣的上界比實際可行解大或等於、可快速計算，並且能有效幫助剪枝。 剪枝條件（Pruning）

當某個節點的上界 ≤ 目前已知的最佳總價值（best value），就可以剪枝，因為這個節點不可能得到更好的解。

貪婪演算法核心概念

在每一步都做出當下最有利的局部選擇，期望最終能接近全域最優解。在多重背包問題中，通常是根據價值密度（value per unit weight）排序物品，並將其放入還能容納的背包中。

定義價值密度

分配物品方式 對排序後的每個物品 i：

• 遍歷背包 j=1 到 m
• 如果背包 j 的剩餘容量 ≥w_i，則：
  • 把物品 i 放入背包 j
  • 更新背包 j 的剩餘容量
  • 記錄該分配
  • 跳出背包迴圈（一個物品只能放進一個背包）

改進與優化

為提升基本貪婪演算法在多重背包問題中的解品質，可考慮多種改進策略。首先，在背包選擇上，不再僅將物品放入第一個可行背包，而是優先選擇剩餘容量最剛好或剩餘容量最多的背包，以減少空間浪費或保留配置彈性。其次，可實施雙層排序貪婪策略：物品依據價值密度排序，背包則依據剩餘容量動態排序，透過更合適的搭配提升整體效益。最後，可結合局部重配（Local Reassignment）機制，在初始解產生後，針對特定物品調整其背包分配，或替換低效物品以提升總價值，類似模擬退火中的鄰域搜尋，但限制在局部範圍內進行。這些強化策略能在不顯著增加時間複雜度的情況下，有效改善解的品質與資源使用效率。