一篇文章带你学透动态规划背包问题

​个人主页zephyr05个人专栏Linux C/C 竞赛专栏座右铭等风来不如追风去追寻的过程就是人生的意义。目录一、题目标准描述01背包完全背包二、例题解析01背包题目链接完全背包题目链接三、总结一、题目标准描述01背包核心特征每种物品只有一件可以选择放入或不放入不能拆分。标准题目描述有N件物品和一个容量为V的背包。每件物品只能使用一次。第i件物品的体积是v_i价值是w_i。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。输入/输出格式示例输入格式第一行两个整数NV分别表示物品数量和背包容积。接下来N行每行两个整数v_iw_i表示第i件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0 N, V ≤ 10000 v_i, w_i ≤ 100完全背包核心特征每种物品都有无限件可用同一种物品可以多次选取。标准题目描述有N种物品和一个容量为V的背包每种物品都有无限件可用。第i种物品的体积是v_i价值是w_i。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量且价值总和最大。输入/输出格式示例输入格式第一行两个整数NV分别表示物品数量和背包容积。接下来N行每行两个整数v_iw_i表示第i件物品的体积和价值。输出格式输出一个整数表示最大价值。数据范围0 N, V ≤ 10000 v_i, w_i ≤ 1000二、例题解析01背包题目链接确认状态表示dp[i][j]表示从前i个物品中挑选总体积不超过j此时的最大重量。状态转移方程答案返回dp[n][V]的值初始化循环范围i 从 1~nj 从 1~V代码class Solution { int dp[1010][1010]{0}; public: int knapsack(int V, int n, vectorvectorint vw) { for(int i1;in;i){ for(int j1;jV;j){ dp[i][j]dp[i-1][j]; if(jvw[i-1][0]) dp[i][j]max(dp[i-1][j],dp[i-1][j-vw[i-1][0]]vw[i-1][1]); //注意这里dp[i]对应的物品i在vw中的下标是i-1 } } return dp[n][V]; } };空间优化观察状态转移方程不难发现每一轮循环的dp[i]的值都依赖于上一轮的dp[i-1]的值既然如此我们可以采用滚动数组的方式将二维数组优化为一维数组。此时dp[j]的意义为i1时j从1到V最大重量i2时j从1到V最大重量 ... 以此类推外层循环i 从1到ndp[j]不断更新直到in时j从1到V最大重量。此时答案就是dp[V]。状态转移方程初始化dp[0]0循环范围特别要注意空间优化版本的j应该逆序循环因为根据状态转移方程dp[j]的更新依赖于dp[j-vw[i]]如果我们正序更新dp[j]的值那dp[j-vw[i]]就会先更新此时dp[j-vw[i]]的值就是考虑了第i个物品之后的值而我们需要的是只考虑前i-1个物品的dp[j-vw[i]]但是这个值已经被覆盖了。当我们更新dp[j]时第i个物品可能在dp[j-vw[i]]时就选择了一次在dp[j]时又可能被选择一次那最终的结果就会明显偏大。逆序循环就是为了先更新dp[j]再更新dp[j-vw[i]]。代码class Solution { int dp[1010]{0}; public: int knapsack(int V, int n, vectorvectorint vw) { for(int i1;in;i){ for(int jV;jvw[i-1][0];j--){ dp[j]max(dp[j],dp[j-vw[i-1][0]]vw[i-1][1]); } } return dp[V]; } };完全背包题目链接状态表示dp[i][j]表示从前i个面值的硬币中选总金额不超过j此时的最少硬币数。状态转移方程对比01背包其实唯一的区别的就是选择i的时候完全背包每件物品可以无限次选取所以还是dp[i][*]答案dp[n][amount]初始化j0时需要0个物品就可以达到要求i0 且j≠0时从0个物品中选择总金额达到j需要无限个物品。所以初始化数组的时候要给数组成员初始化一个很大的值。循环范围i 从 1~n j 从 1~amount代码class Solution { public: int coinChange(vectorint coins, int amount) { int ncoins.size(); vectorvectorint dp(n1,vectorint(amount1,10010)); for(int i1;in;i){ for(int j0;jamount;j){ if(j0) dp[i][j]0; else{ int valcoins[i-1]; dp[i][j]dp[i-1][j]; if(jval) dp[i][j]min(dp[i-1][j],dp[i][j-val]1); } } } return dp[n][amount] 10010 ? -1 : dp[n][amount]; } };空间优化和01背包同理利用滚动数组将二维数组优化为一维数组状态转移方程初始化dp[0]0循环范围注意完全背包j的循环顺序一定要正序循环刚好和01背包是反过来的因为物品可以无限次选取正序循环就可以满足这一点。代码class Solution { public: int coinChange(vectorint coins, int amount) { int ncoins.size(); vectorint dp(amount1,10010); dp[0]0; for(int i1;in;i){ for(int jcoins[i-1];jamount;j){ int valcoins[i-1]; dp[j]min(dp[j],dp[j-val]1); } } return dp[amount] 10010 ? -1 : dp[amount]; } };三、总结力扣上的背包问题很少会直接以“纯01背包”或“纯完全背包”的裸题形式出现更多时候它们被包装在各种应用题里需要你自己识别并转化为背包模型。因此死记硬背公式解法并不可取真正重要的是理解背包问题背后的核心原理掌握其思维范式——这样当遇到变形题目时你才能灵活地将它还原为熟悉的背包结构。在我看来背包问题乃至所有动态规划问题最大的难点都在于如何找到合适的状态表示。这种能力不是靠记住几个模板就能获得的它需要大量针对性的刷题训练在反复试错中逐渐培养出“题感”。算法学习远不止于刷题本身。每一次错误、每一回卡壳都是沉淀思考的契机。从错误中复盘在总结中提炼才能真正把知识内化。希望这篇梳理能帮你少走一些弯路更扎实地理解这两种基础背包算法的精髓。如果本文对你有帮助欢迎点赞、收藏、分享。如有疑问请在评论区留言我会尽力解答。博客首发于 CSDN转载请注明出处。