网站页面热度,企业网站开发背景,国内室内设计网站大全,对外贸网站建设的建议背包问题
-返回c/c蓝桥杯经典编程题100道-目录 目录
背包问题
一、题型解释
二、例题问题描述
三、C语言实现
解法1#xff1a;0-1背包#xff08;基础动态规划#xff0c;难度★#xff09;
解法2#xff1a;0-1背包#xff08;空间优化版#xff0c;难度★…背包问题
-返回c/c蓝桥杯经典编程题100道-目录 目录
背包问题
一、题型解释
二、例题问题描述
三、C语言实现
解法10-1背包基础动态规划难度★
解法20-1背包空间优化版难度★★
解法3完全背包难度★★
四、C实现
解法10-1背包STL vector版难度★☆
解法2多重背包二进制优化难度★★★
五、总结对比表
六、特殊方法与内置函数补充
1. C STL的 max 函数
2. 滚动数组优化
3. 单调队列优化 一、题型解释
背包问题是动态规划中的经典问题核心是 在限定容量下选择物品使得总价值最大化。常见变种 0-1背包每个物品只能选或不选每个物品1个。 完全背包每个物品可以选无限次。 多重背包每个物品最多选指定次数。 分组背包每组物品中只能选一个。 二、例题问题描述
例题10-1背包 容量 W4物品重量 [1,3,4]价值 [15,20,30]输出最大价值 35选物品0和2。
例题2完全背包 容量 W5物品重量 [1,2]价值 [15,20]输出最大价值 75选5个物品0。
例题3多重背包 容量 W10物品重量 [2,3]价值 [5,7]数量 [2,3]输出最大价值 24选3个物品1。
例题4分组背包 容量 W6分组物品 [[1,2], [3,4]]每组选一个输出最大价值 6选第一组2第二组4。 三、C语言实现
解法10-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;
}
代码逻辑 初始化DP表dp[i][j] 表示前 i 个物品在容量 j 下的最大价值。 填表规则 物品超重时继承上一行结果。 否则取“不选”和“选”的最大值。 解法20-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];
}
代码逻辑 一维数组dp[j] 表示容量 j 的最大价值。 逆序遍历确保每个物品只被选一次。 解法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实现
解法10-1背包STL vector版难度★☆
通俗解释 使用 vector 替代数组动态管理内存避免固定大小限制。
cpp
#include iostream
#include vector
using namespace std;int knapsack01STL(int W, vectorint wt, vectorint val) {vectorint 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() {vectorint wt {1,3,4}, val {15,20,30};int W 4;cout 0-1背包最大价值 knapsack01STL(W, wt, val) endl; // 输出35return 0;
}
代码逻辑 与C语言空间优化版相同但使用 vector 动态管理内存。 解法2多重背包二进制优化难度★★★
通俗解释 将物品数量拆分为二进制组合如7124转化为0-1背包问题。
cpp
int multiKnapsack(int W, vectorint wt, vectorint val, vectorint cnt) {vectorint 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() {vectorint wt {2,3}, val {5,7}, cnt {2,3};int W 10;cout 多重背包最大价值 multiKnapsack(W, wt, val, cnt) endl; // 输出24return 0;
}
代码逻辑 二进制拆分将数量拆分为2的幂次之和减少物品数量。 转化为0-1背包对每个拆分后的物品进行0-1背包处理。 五、总结对比表
方法时间复杂度空间复杂度优点缺点0-1背包基础DPO(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道-目录
