先来看模版题目1.小明的背包1这个便是最经典的求最大价值的01背包问题暴力求解的话便是dfs每个选或不选决策树的问题这个时间复杂度太高了暂且不说。设dp[i][j]为前i个物品装进容量为j的背包所能产生的最大价值接下来考虑状态转移方程假设某种放的方法成功达到了最大值对于这个方法对于第i个物品来说有两种可能的情况第一种是这种方法包括他第二种是不包括取两种方法的最大值如果放入第i个物品的话那么获得第i个物品的价值接下来的背包就是从前i-1个元素中选择若干物品放入容量为v-w[i]的背包中如果不放入那么便是从i-1个物品中放入容量为v的背包中即dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]c[i]);边界处理问题这里边界的处理是由转移方程得到的其实第二个for循环可以不用赋值10086也是能通过的dp[0][0]0; for(int i1;iv;i){ dp[0][i]0; } for(int i1;in;i){ dp[i][0]0; }接下来来看状态转移的代码实现for(int i1;in;i){ for(int j0;jv;j){ if(jw[i]) dp[i][j]dp[i-1][j]; else dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]c[i]); } }这里要考虑jw[i]时是一定不能选的这道题目还可以进行空间优化因为这里状态转移方程只取决于上一维度的dp数组这里j要从大到小遍历否则每次更新将会覆盖上一层的元素而这些元素可能在j更大时需要用到for(int i0;iv;i){ dp[i]0; } for(int i1;in;i){ for(int jv;j0;j--){ if(jw[i]) dp[j]max(dp[j],dp[j-w[i]]c[i]); } }01背包的进阶问题完全背包这里物品不再是以1个了而是可以无限去选择了1.小明的背包2 - 蓝桥云课对于完全背包来说dp数组的状态定义是不变的但是状态转移方程要变了这里如果选择拿的话就要枚举所有能拿的情况一个或者两个或者更多for(int i1;in;i){ for(int j0;jv;j){ dp[i][j]0; for(int k0;kj/w[i];k){ dp[i][j]max(dp[i][j],k*c[i]dp[i-1][j-k*w[i]]); } }完全背包的空间优化时间优化先看时间优化对于第i个商品拿或者不拿也可以看成不拿以及至少拿一个既然是至少拿一个的话那可以先放一个进背包就变成了dp[i][j-w[i]]c[i]for(int i1;in;i){ for(int j1;jv;j){ if(jw[i]) dp[i][j]dp[i-1][j]; else dp[i][j]max(dp[i-1][j],dp[i][j-w[i]]c[i]); } }同时空间也可以优化注意这里就要从小到大遍历了dp[j-w[i]]c[i]这个是同一行的结果而非要上一行的结果。for(int i0;iv;i){ dp[i]0; } for(int i1;in;i){ for(int j0;jv;j){ if(jw[i]) dp[j]max(dp[j],dp[j-w[i]]c[i]); } }背包dp的变种问题1不再求最大价值转而去求有多少种方案数的问题U663298 疯狂的背包问题(3) - 01背包问题计数组合问题 - 洛谷这里dp数组的状态定义就要由最大价值改为方案数了#includebits/stdc.h using namespace std; #define int long long int ans0; int dp[1001][1001]; //dp[i][j]dp[i-1][j]dp[i-1][j-w[i]]; int w[1001]; signed main(){ int n,m; cinnm; for(int i1;in;i){ cinw[i]; } dp[0][0]1; for(int i1;im;i){ dp[0][i]0; } for(int i1;in;i){ for(int j0;jm;j){ if(jw[i]) dp[i][j](dp[i-1][j]dp[i-1][j-w[i]])%1000000007; else dp[i][j]dp[i-1][j]%1000000007; } } coutdp[n][m]%1000000007; return 0; }2,无限背包变种518. 零钱兑换 II - 力扣LeetCode作者最近几天用脑过度了待更新。。。到这里背包 dp 的核心内容就梳理得差不多了。我们从最经典的 01 背包出发理解了状态定义、状态转移方程和边界处理也掌握了空间优化的思路接着扩展到完全背包看到了枚举拿取数量的朴素写法以及时间、空间上的双重优化最后还介绍了背包 dp 的常见变种比如求方案数的问题。背包 dp 是动态规划里非常基础也非常重要的一类模型很多看似复杂的问题最终都能化归到背包的框架下求解。希望这篇总结能帮你把背包 dp 的脉络理清楚也欢迎在评论区交流你的想法后续我会继续补充更多变种和实战题目。