背包問題

->返回c/c++藍橋杯經典編程題100道-目錄

---

目錄

背包問題

一、題型解釋

二、例題問題描述

三、C語言實現

解法1：0-1背包（基礎動態規劃，難度★）

解法2：0-1背包（空間優化版，難度★★）

解法3：完全背包（難度★★）

四、C++實現

解法1：0-1背包（STL vector版，難度★☆）

解法2：多重背包（二進制優化，難度★★★）

五、總結對比表

六、特殊方法與內置函數補充

1. C++ STL的?max?函數

2. 滾動數組優化

3. 單調隊列優化

---

一、題型解釋

背包問題是動態規劃中的經典問題，核心是?在限定容量下選擇物品使得總價值最大化。常見變種：

1. 0-1背包：每個物品只能選或不選（每個物品1個）。

2. 完全背包：每個物品可以選無限次。

3. 多重背包：每個物品最多選指定次數。

4. 分組背包：每組物品中只能選一個。

---

二、例題問題描述

例題1（0-1背包）：

• 容量?W=4，物品重量?[1,3,4]，價值?[15,20,30]，輸出最大價值?35（選物品0和2）。

例題2（完全背包）：

• 容量?W=5，物品重量?[1,2]，價值?[15,20]，輸出最大價值?75（選5個物品0）。

例題3（多重背包）：

• 容量?W=10，物品重量?[2,3]，價值?[5,7]，數量?[2,3]，輸出最大價值?24（選3個物品1）。

例題4（分組背包）：

• 容量?W=6，分組物品?[[1,2], [3,4]]（每組選一個），輸出最大價值?6（選第一組2，第二組4）。

---

三、C語言實現

解法1：0-1背包（基礎動態規劃，難度★）

通俗解釋：

• 填表格記錄不同容量下的最大價值，像存錢罐一樣逐步塞入物品。

c

#include <stdio.h>
#include <string.h>#define MAX_W 100
#define MAX_N 100int max(int a, int b) { return a > b ? a : b; }int knapsack01(int W, int wt[], int val[], int n) {int dp[MAX_N][MAX_W]; // dp[i][j]：前i個物品，容量j的最大價值memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; i++) {for (int j = 1; j <= W; j++) {if (wt[i-1] > j) { // 當前物品超重，無法選擇dp[i][j] = dp[i-1][j];} else { // 能選：比較選或不選的價值dp[i][j] = max(dp[i-1][j], dp[i-1][j - wt[i-1]] + val[i-1]);}}}return dp[n][W];
}int main() {int W = 4;int wt[] = {1,3,4}, val[] = {15,20,30};int n = sizeof(wt)/sizeof(wt[0]);printf("0-1背包最大價值：%d\n", knapsack01(W, wt, val, n)); // 輸出35return 0;
}

代碼邏輯：

1. 初始化DP表：dp[i][j]?表示前?i?個物品在容量?j?下的最大價值。

2. 填表規則：

   • 物品超重時，繼承上一行結果。

   • 否則，取“不選”和“選”的最大值。

---

解法2：0-1背包（空間優化版，難度★★）

通俗解釋：

• 僅用一維數組，倒序遍歷容量，避免覆蓋未計算的數據。

c

int knapsack01Optimized(int W, int wt[], int val[], int n) {int dp[MAX_W] = {0};for (int i = 0; i < n; i++) { // 遍歷物品for (int j = W; j >= wt[i]; j--) { // 逆序更新，防止重復選dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);}}return dp[W];
}

代碼邏輯：

1. 一維數組：dp[j]?表示容量?j?的最大價值。

2. 逆序遍歷：確保每個物品只被選一次。

---

解法3：完全背包（難度★★）

通俗解釋：

• 正序遍歷容量，允許重復選擇物品，像存錢罐可以多次塞硬幣。

c

int completeKnapsack(int W, int wt[], int val[], int n) {int dp[MAX_W] = {0};for (int i = 0; i < n; i++) {for (int j = wt[i]; j <= W; j++) { // 正序更新，允許重復選dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);}}return dp[W];
}int main() {int W = 5;int wt[] = {1,2}, val[] = {15,20};int n = sizeof(wt)/sizeof(wt[0]);printf("完全背包最大價值：%d\n", completeKnapsack(W, wt, val, n)); // 輸出75return 0;
}

代碼邏輯：

• 正序遍歷：允許同一物品多次被選中。

---

四、C++實現

解法1：0-1背包（STL vector版，難度★☆）

通俗解釋：

• 使用?vector?替代數組，動態管理內存，避免固定大小限制。

cpp

#include <iostream>
#include <vector>
using namespace std;int knapsack01STL(int W, vector<int>& wt, vector<int>& val) {vector<int> dp(W + 1, 0);for (int i = 0; i < wt.size(); i++) {for (int j = W; j >= wt[i]; j--) { // 逆序更新dp[j] = max(dp[j], dp[j - wt[i]] + val[i]);}}return dp[W];
}int main() {vector<int> wt = {1,3,4}, val = {15,20,30};int W = 4;cout << "0-1背包最大價值：" << knapsack01STL(W, wt, val) << endl; // 輸出35return 0;
}

代碼邏輯：

• 與C語言空間優化版相同，但使用?vector?動態管理內存。

---

解法2：多重背包（二進制優化，難度★★★）

通俗解釋：

• 將物品數量拆分為二進制組合（如7=1+2+4），轉化為0-1背包問題。

cpp

int multiKnapsack(int W, vector<int>& wt, vector<int>& val, vector<int>& cnt) {vector<int> dp(W + 1, 0);for (int i = 0; i < wt.size(); i++) {int k = 1;int remain = cnt[i];while (k <= remain) { // 二進制拆分int w = wt[i] * k;int v = val[i] * k;for (int j = W; j >= w; j--) {dp[j] = max(dp[j], dp[j - w] + v);}remain -= k;k *= 2;}if (remain > 0) { // 處理剩余數量int w = wt[i] * remain;int v = val[i] * remain;for (int j = W; j >= w; j--) {dp[j] = max(dp[j], dp[j - w] + v);}}}return dp[W];
}int main() {vector<int> wt = {2,3}, val = {5,7}, cnt = {2,3};int W = 10;cout << "多重背包最大價值：" << multiKnapsack(W, wt, val, cnt) << endl; // 輸出24return 0;
}

代碼邏輯：

1. 二進制拆分：將數量拆分為2的冪次之和，減少物品數量。

2. 轉化為0-1背包：對每個拆分后的物品進行0-1背包處理。

---

五、總結對比表

方法	時間復雜度	空間復雜度	優點	缺點
0-1背包基礎DP	O(nW)	O(nW)	直觀易理解	內存占用高
0-1背包空間優化	O(nW)	O(W)	內存高效	無法回溯具體方案
完全背包	O(nW)	O(W)	支持無限次選擇	不適用0-1場景
多重背包優化	O(nW logS)	O(W)	處理數量限制	實現較復雜

---

六、特殊方法與內置函數補充

1. C++ STL的?max?函數

• 用法：max(a, b)?返回較大值，需包含?<algorithm>?頭文件。

2. 滾動數組優化

• 原理：利用奇偶行交替存儲，將二維DP壓縮為兩個一維數組。

3. 單調隊列優化

• 適用場景：多重背包的進一步優化，時間復雜度降至O(nW)。

->返回c/c++藍橋杯經典編程題100道-目錄