提高网站收录的方法百度认证号码平台

背包问题

->返回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道-目录