背包問題模型中多重背包是介于0/1背包（每種物品1個）和完全背包（每種物品無限個）之間的中間態——它允許每種物品選擇有限次（如每種物品最多選3個），這種模型更貼近現實場景（如“商品限購”“物資有限”），但解法復雜度更高。

一、多重背包基礎認知

1.1 問題定義

給定n種物品，每種物品有重量w[i]、價值v[i]和數量上限cnt[i]；背包容量為C。每種物品最多選擇cnt[i]次，求在總重量不超過C的前提下，能裝入物品的最大總價值。

示例：

• 輸入：n=2, C=10, w=[3,4], v=[5,6], cnt=[2,2]（物品0最多2個，物品1最多2個）
• 輸出：17（選擇2個物品0（3×2=6重量，5×2=10價值）和1個物品1（4重量，6價值），總重量6+4=10，總價值10+6=16？最優應為2個物品1（4×2=8重量，6×2=12）+1個物品0（3重量，5）→ 總重量11>10；正確最優：2個物品0（6重量，10）+1個物品1（4重量，6）→ 總重量10，價值16？或1個物品0（3）+2個物品1（8）→ 總重量11>10，因此正確輸出16）

1.2 核心特征

• 數量限制：每種物品有明確的選擇上限（cnt[i]），區別于0/1背包（cnt[i]=1）和完全背包（cnt[i]=+∞）。
• 容量約束：總重量≤C，與其他背包模型一致。
• 優化目標：在數量和容量雙重約束下最大化總價值。

多重背包的本質是“帶數量和容量雙重約束的物品選擇優化”，其基礎解法可通過0/1背包擴展得到，但直接實現效率較低，需通過“二進制拆分”優化。

二、基礎解法：暴力拆分

2.1 核心思路

多重背包可直接轉化為0/1背包：將每種物品按數量上限cnt[i]拆分為cnt[i]個獨立物品（每個物品只能選1次），然后用0/1背包的解法求解。

例如：物品0（w=3, v=5, cnt=2）可拆分為2個相同物品：(3,5)和(3,5)，后續按0/1背包處理（每個物品最多選1次）。

2.2 代碼實現

public class MultipleKnapsack {/*** 多重背包基礎實現（暴力拆分）* @param n 物品種類數* @param C 背包容量* @param w 重量數組* @param v 價值數組* @param cnt 數量上限數組* @return 最大價值*/public int maxValue(int n, int C, int[] w, int[] v, int[] cnt) {// 步驟1：暴力拆分物品（轉化為0/1背包物品列表）List<Integer> newW = new ArrayList<>();List<Integer> newV = new ArrayList<>();for (int i = 0; i < n; i++) {// 將第i種物品拆分為cnt[i]個for (int k = 0; k < cnt[i]; k++) {newW.add(w[i]);newV.add(v[i]);}}// 步驟2：用0/1背包求解int[] dp = new int[C + 1];for (int i = 0; i < newW.size(); i++) {int currW = newW.get(i);int currV = newV.get(i);// 0/1背包逆序遍歷for (int j = C; j >= currW; j--) {dp[j] = Math.max(dp[j], dp[j - currW] + currV);}}return dp[C];}public static void main(String[] args) {MultipleKnapsack solver = new MultipleKnapsack();int n = 2;int C = 10;int[] w = {3, 4};int[] v = {5, 6};int[] cnt = {2, 2};System.out.println(solver.maxValue(n, C, w, v, cnt)); // 輸出16}
}

2.3 局限性分析

• 時間復雜度：設物品總數量為N = sum(cnt[i])，則復雜度為O(N×C)。當cnt[i]較大（如cnt[i]=1000）時，N可達10^6，C=10^4時總操作次數為10^10，嚴重超時。
• 空間復雜度：拆分后物品列表需存儲N個物品，內存占用大。

因此，暴力拆分僅適用于cnt[i]較小的場景（如cnt[i]≤10），需更高效的優化方法。

三、優化解法：二進制拆分

3.1 優化原理

二進制拆分的核心是“用少量物品組合表示所有可能的選擇次數”，避免暴力拆分的冗余。

例如：cnt=5（最多選5個），可拆分為1、2、2（1+2+2=5）：

• 選0個：不選任何拆分物品；
• 選1個：選1；
• 選2個：選2；
• 選3個：選1+2；
• 選4個：選2+2；
• 選5個：選1+2+2。

通過2^0, 2^1, ..., 2^k, r（r為剩余數量）的拆分方式，可覆蓋0~cnt的所有選擇次數，且拆分后物品數從cnt降至log2(cnt)（如cnt=1000僅需10個拆分物品）。

3.2 拆分步驟

對每種物品i（數量cnt[i]）：

1. 初始化k=1（從2^0開始）；
2. 若k ≤ cnt[i]，則拆分出一個重量k×w[i]、價值k×v[i]的物品，cnt[i] -= k，k *= 2；
3. 若cnt[i] > 0，則拆分出一個重量cnt[i]×w[i]、價值cnt[i]×v[i]的物品；
4. 拆分后的物品按0/1背包處理（每個拆分物品最多選1次）。

3.3 代碼實現

public class MultipleKnapsackOptimized {/*** 多重背包優化實現（二進制拆分）* @param n 物品種類數* @param C 背包容量* @param w 重量數組* @param v 價值數組* @param cnt 數量上限數組* @return 最大價值*/public int maxValue(int n, int C, int[] w, int[] v, int[] cnt) {// 步驟1：二進制拆分物品List<Integer> newW = new ArrayList<>();List<Integer> newV = new ArrayList<>();for (int i = 0; i < n; i++) {int currW = w[i];int currV = v[i];int currCnt = cnt[i];// 二進制拆分：k=1,2,4,...for (int k = 1; k <= currCnt; k *= 2) {newW.add(k * currW);newV.add(k * currV);currCnt -= k;}// 剩余數量拆分if (currCnt > 0) {newW.add(currCnt * currW);newV.add(currCnt * currV);}}// 步驟2：0/1背包求解int[] dp = new int[C + 1];for (int i = 0; i < newW.size(); i++) {int currW = newW.get(i);int currV = newV.get(i);for (int j = C; j >= currW; j--) {dp[j] = Math.max(dp[j], dp[j - currW] + currV);}}return dp[C];}public static void main(String[] args) {MultipleKnapsackOptimized solver = new MultipleKnapsackOptimized();int n = 2;int C = 10;int[] w = {3, 4};int[] v = {5, 6};int[] cnt = {2, 2};System.out.println(solver.maxValue(n, C, w, v, cnt)); // 輸出16}
}

3.4 復雜度分析

• 時間復雜度：拆分后物品總數N' = sum(log2(cnt[i]))，若cnt[i]≤1000，n=100，則N'≈100×10=1000，C=10^4時總操作次數為1000×10^4=10^7，效率大幅提升。
• 空間復雜度：O(N' + C)，N'遠小于暴力拆分的N。

二進制拆分是多重背包的標準優化方法，適用于cnt[i]較大的場景（cnt[i]≤10^5均可處理）。

四、二進制拆分過程

以示例中“物品0（w=3, v=5, cnt=2）”為例：

1. 拆分cnt=2：
   • k=1：1 ≤ 2，拆分出(1×3, 1×5)=(3,5)，currCnt=2-1=1；
   • k=2：2 > 1，停止循環；
   • 剩余currCnt=1，拆分出(1×3, 1×5)=(3,5)；
   • 拆分后物品：[(3,5), (3,5)]（與暴力拆分相同，因cnt較小）。

以“物品（cnt=5）”為例：

1. 拆分cnt=5：
   • k=1：拆分(1w, 1v)，currCnt=5-1=4；
   • k=2：拆分(2w, 2v)，currCnt=4-2=2；
   • k=4：4 > 2，停止循環；
   • 剩余currCnt=2：拆分(2w, 2v)；
   • 拆分后物品：(1w,1v), (2w,2v), (2w,2v)（3個物品，覆蓋0~5所有選擇）。

五、多重背包的變種與應用

5.1 變種問題

1. 混合背包（0/1+完全+多重）：

   • 問題：物品可能是0/1（cnt=1）、完全（cnt=+∞）或多重（1<cnt<+∞）。
   • 解法：分類處理——0/1直接加、完全按正序、多重二進制拆分后按0/1處理。

2. 二維多重背包（重量+體積約束）：

   • 問題：物品有重量和體積兩個約束，需同時滿足。
   • 解法：用二維DP數組dp[j][k]（j為重量，k為體積），拆分后按二維0/1背包處理。

3. 數量下限約束：

   • 問題：每種物品至少選minCnt[i]個，最多選maxCnt[i]個。
   • 解法：先強制選minCnt[i]個（扣除容量和價值），剩余數量按maxCnt[i]-minCnt[i]的多重背包處理。

5.2 應用場景

• 商品限購：如“每人最多買3件”，用多重背包選擇最優組合。
• 物資分配：如“倉庫有5臺設備，每臺重量10，價值20”，有限運力下最大化運輸價值。
• 資源打包：如“零件按包出售（每包2個），最多買4包”，轉化為多重背包（cnt=4，每包視為拆分后的物品）。

三種背包的區別

模型	物品選擇次數	核心解法	時間復雜度（優化后）
0/1背包	最多1次	逆序遍歷容量	O(n×C)
完全背包	無限次	正序遍歷容量	O(n×C)
多重背包	最多cnt[i]次	二進制拆分+0/1背包	O(sum(log cnt[i]) × C)

總結

多重背包的核心是“數量限制下的物品選擇”，其解法的關鍵是通過“二進制拆分”將問題高效轉化為0/1背包，避免暴力拆分的冗余：

1. 基礎解法：暴力拆分為0/1背包，僅適用于cnt[i]較小的場景。
2. 優化解法：二進制拆分通過2^k組合覆蓋所有選擇次數，將復雜度從O(N×C)降至O(sum(log cnt[i])×C)。
3. 變種遷移：混合背包、二維約束等變種可通過分類處理和維度擴展解決。

That’s all, thanks for reading~~
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～