文章目录一、背包问题核心概念1.1 问题场景与分类1.2 动态规划解题核心二、01背包三、完全背包物品可重复选四、多重背包核心逻辑四、二维数组实现五、全文总结背包问题是动态规划领域最经典的入门题型核心逻辑是在有限背包容量内选取物品实现总价值最大化。吃透背包问题不仅能夯实数组、循环、递归等基础语法更能建立动态规划的解题思维为后续复杂算法学习铺路。本文聚焦最常用的01背包问题物品不可重复选取顺带延伸讲解完全背包物品可无限选取以及特殊的多重背包问题全程搭配C语言完整可运行代码、逐行详解注释和清晰思路拆解并用经典例题辅助理解。一、背包问题核心概念1.1 问题场景与分类假设我们有一个最大容量为 W 的背包同时有 n 件互不相同的物品每件物品都对应两个属性重量weight[i] 和 价值value[i]。根据物品选取规则背包问题主要分为两类01背包每件物品仅有一个只能选择放或者不放不可拆分、不可重复选取完全背包每件物品数量无限可重复选取多件放入背包两类问题的共同目标在不超出背包容量的前提下让装入物品的总价值达到最大。1.2 动态规划解题核心暴力枚举所有物品组合会产生大量冗余计算时间复杂度极高而动态规划的精髓就是拆分子问题状态转移用空间换时间高效求解最优解。先定义核心状态dp[j] 表示背包容量为j 时能装入物品的最大价值。01背包的状态转移方程d p [ j ] max ⁡ ( d p [ j ] , d p [ j − w e i g h t [ i ] ] v a l u e [ i ] ) dp[j] \max(dp[j],\ dp[j - weight[i]] value[i])dp[j]max(dp[j],dp[j−weight[i]]value[i])方程含义面对第 i 件物品时我们有两种选择——不放入该物品此时最大价值保持原有 dp[j] 不变放入该物品此时需要预留出物品重量用剩余容量的最大价值加上当前物品价值最终取两种选择的最大值。关键区分技巧01背包需逆序遍历背包容量避免重复选同一物品完全背包需正序遍历容量支持物品重复选取这是两类代码的核心差异。二、01背包一维数组优化是笔试、工程中最常用的写法相比二维数组更节省内存空间逻辑也更简洁。这里我们选用经典例题对标卡码网46题样例原题链接https://kamacoder.com/problempage.php?pid1046// 定义最大值宏方便状态转移取最大#defineMAX(a,b)((a)(b)?(a):(b))stdio.hstdlib.hintmain(){// M物品个数N背包容量intM,N;scanf(%d %d,M,N);// 动态分配数组存储物品体积和价值int*volumemalloc(sizeof(int)*M);int*valuemalloc(sizeof(int)*M);// 读取物品体积数据for(inti0;iM;i){scanf(%d,volume[i]);}// 读取物品价值数据for(inti0;M;i){scanf(%d,value[i]);}// dp[j]容量为j的背包能装的最大价值int*dpmalloc(sizeof(int)*(N1));// dp数组初始化容量为0时价值为0for(inti0N;i){dp[i]0;}// 遍历每件物品01背包核心for(inti0M;i){// 逆序遍历容量避免重复选取同一个物品for(intjN;j0;j--){// 物品体积大于当前背包容量放不下保持原值if(volume[i]j){dp[j]dp[j];}else{// 能放下选当前物品 vs 不选取最大价值dp[j]MAX(dp[j],dp[j-volume[i]]value[i]);}}}// 输出背包最大价值printf(%d,dp[N]);// 释放动态内存防止泄漏free(value);free(volume);free(dp);return0;}三、完全背包物品可重复选完全背包与01背包的代码逻辑高度相似仅需修改容量遍历顺序将逆序改为正序就能实现物品重复选取无需改动其他代码。这里以卡码网第52题为例。原题链接https://kamacoder.com/problempage.php?pid1052// 定义最大值宏状态转移时取较大值#defineMAX(a,b)((a)(b)?(a):(b))#includestdio.h#includestdlib.hintmain(){// n物品数量 v背包最大容量intn,v;// 输入物品数量和背包容量scanf(%d %d,n,v);// 动态分配数组存储物品重量、价值int*weightmalloc(sizeof(int)*n);int*valuemalloc(sizeof(int)*n);// 循环读取每个物品的重量和价值for(inti0;in;i){scanf(%d %d,weight[i],value[i]);}// dp[j]容量为j的背包能装入的最大价值初始化为0int*dpmalloc(sizeof(int)*(v1));for(inti0;iv;i){dp[i]0;}// 完全背包核心逻辑遍历每件物品for(inti0;in;i){// 正序遍历容量关键允许同一物品被重复选取for(intj0;jv;j){// 物品重量≤当前容量时尝试放入并更新最大价值if(weight[i]j){dp[j]MAX(dp[j],dp[j-weight[i]]value[i]);}}}// 输出背包容量v下的最大价值printf(%d,dp[v]);// 释放动态内存避免内存泄漏free(weight);free(value);free(dp);return0;}四、多重背包多重背包是 01 背包和完全背包的中间形态 —— 每件物品既不是只能选 1 次01 背包也不是无限次选取完全背包而是有明确的数量限制比如物品 A 最多选 3 个、物品 B 最多选 5 个也是常见的背包变种题型。核心逻辑多重背包的解题思路可理解为「01 背包的延伸」把每件有数量限制的物品拆解成「多个独立的相同物品」再用 01 背包的逻辑求解。比如 “物品 A 重量 2、价值 3最多选 2 个”可拆解为 “物品 A1重量 2、价值 3 物品 A2重量 2、价值 3”再按 01 背包选 / 不选的规则处理。高效的实现方式是「三层循环」外层遍历每件物品中层逆序遍历背包容量同 01 背包防止重复选取内层遍历当前物品的可选数量不超过自身数量限制也不超过背包容量。这里以卡码网第56题为例原题链接https://kamacoder.com/problempage.php?pid1066#includestdio.h#includestdlib.h#includestring.h#defineMAX(a,b)((a)(b)?(a):(b))intmain(){// 1. 处理输入异常兼容所有输入格式intc0,n0;if(scanf(%d,c)!1||scanf(%d,n)!1){printf(0\n);return0;}// 2. 处理n0无物品if(n0){printf(0\n);return0;}// 3. 申请内存int*weight(int*)malloc(sizeof(int)*n);int*value(int*)malloc(sizeof(int)*n);int*num(int*)malloc(sizeof(int)*n);if(weightNULL||valueNULL||numNULL){printf(0\n);return0;}memset(weight,0,sizeof(int)*n);memset(value,0,sizeof(int)*n);memset(num,0,sizeof(int)*n);// 4. 读取物品信息for(inti0;in;i){intw0,v0,cnt0;if(scanf(%d,w)!1)break;if(scanf(%d,v)!1)break;if(scanf(%d,cnt)!1)break;weight[i]w;value[i]v;num[i]cnt;}// 5. 处理c0背包容量为0if(c0){printf(0\n);free(weight);free(value);free(num);return0;}// 6. 初始化dpint*dp(int*)malloc(sizeof(int)*(c1));if(dpNULL){printf(0\n);free(weight);free(value);free(num);return0;}memset(dp,0,sizeof(int)*(c1));// 7. 核心逻辑for(inti0;in;i){// 过滤无效物品if(weight[i]0||value[i]0||num[i]0||weight[i]c){continue;}intidxnum[i];for(intjc;jweight[i];j--){for(intk1;kidx;k){intcostk*weight[i];if(costj)break;// 容量不足提前退出dp[j]MAX(dp[j],dp[j-cost]k*value[i]);}}}// 8. 输出printf(%d\n,dp[c]);// 9. 释放内存free(weight);free(value);free(num);free(dp);return0;}四、二维数组实现一维数组写法虽高效但逻辑偏抽象二维数组写法更直观能清晰看到每一步的状态变化特别适合新手理解动态规划的推导过程。状态定义dp[i][j] 表示前 i 件物品、背包容量为 j 时的最大价值。#includestdio.hintmax(inta,intb){returnab?a:b;}intmain(){intweight[]{1,3,4};intvalue[]{15,20,30};intn3,W4;// 二维dp数组intdp[n1][W1];// 边界初始化for(inti0;in;i)dp[i][0]0;for(intj0;jW;j)dp[0][j]0;// 填充dp数组for(inti1;in;i){for(intj1;jW;j){if(jweight[i-1]){// 容量不足不选当前物品dp[i][j]dp[i-1][j];}else{// 选/不选取最大值dp[i][j]max(dp[i-1][j],dp[i-1][j-weight[i-1]]value[i-1]);}}}printf(最大物品价值%d\n,dp[n][W]);return0;}五、全文总结背包问题作为动态规划的入门经典题型万变不离其宗核心都是在有限背包容量下通过状态转移实现价值最大化。本文详解的01 背包、完全背包、多重背包是最基础也最常用的三类模板吃透三者的逻辑差异和代码写法足以应对绝大多数背包类题目。01 背包是根基每件物品仅可选一次必须逆序遍历背包容量避免重复选取完全背包是延伸物品可无限选取只需将遍历顺序改为正序其余逻辑与 01 背包完全一致多重背包则是二者的结合每件物品有固定选取上限通过三层循环枚举数量本质是带数量约束的 01 背包变种。学习背包问题要理解状态定义的意义、遍历顺序的原因。新手可先从二维数组入门理清状态流转熟练后改用一维优化版提升代码效率。后续遇到分组背包、混合背包等进阶题型均可基于这三类基础模板灵活改造逐步攻克动态规划难关。