2023年8月1日发(作者：)
动态规划——背包问题（详解）动态规划是我最早接触的算法，⼀开始⾮常简单，固定模板题，后来愈发愈发难起来了，条件，状态压缩等等，难点主要是，状态怎么表⽰，状态转移⽅程怎么写，这篇⽂章将会从背包五⼤问题详解，希望能帮助到⼤家去类⽐，思考其他动态规划题⽬。⾸先先来看看动态规划的定义：动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的⽅式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若⼲个⼦问题（阶段），按顺序求解⼦阶段，前⼀⼦问题的解，为后⼀⼦问题的求解提供了有⽤的信息。在求解任⼀⼦问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各⼦问题，最后⼀个⼦问题就是初始问题的解。看完定义我们开始应⽤了！来看基本的01背包问题，也是最经典的动态规划[ps:建议⽽外开个⽹页去打开题⽬链接，⽤Ctrl+tab⾷⽤更佳]这题所求的是V容积下能够装的物品的最⼤值。很显然有容积的限制有时候你不能全部都装，⼜有体积和价值的不确定性，可能你选⼩体积的反⽽会有更⼤的价值，如果去暴⼒枚举时间复杂度呈指数显然不能ac，那么就需要六⼤算法之⼀动态规划了。明确的⼀点此题是求最⼤值，⽽每个物品⾄多选⼀次，也就是只有选和不选俩个状态。我们可以⼀个⼀个物品去决策这个物品是该选还是不该选，这只需要⼀个max函数就能完成了。现在的问题是如何去定义，怎么去记录这个决策过程。依靠现有的知识能储存多组数据的只有数组了，我们可以先定义⼀个⼆维数组dp[N][N]去记录这个过程。int dp[N][N]; //dp[i][j]表⽰容积为j的背包只装前i个物品可以达到的最⼤价值这也是动态规划的第⼀步，明确数组的含义或者集合的含义。接下来可以⼀个⼀个去决策了，先预知⼀下，肯定需要⼀个for循环去枚举物品，枚举完物品⼜需要⼀个for循环去枚举体积。在选或不选的情况下去择优，更新dp[i][j]，n2的时间复杂度，显然对付这题很容易了。for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) { dp[i][j] = dp[i-1][j]; //⼀开始是都选择不装 if(j>=v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]);
//只有物品体积⼤于背包容积了才可以开始决策择优选或不选。 }}那么最终答案就是dp[n][m],在只考虑前n个物品最⼤容积为m的背包可以装的物品的最⼤价值ac代码：#include
}可能有⼈了解到可以空间压缩，滚动数组等等，在此先不讲，我们前⾯先讲思维。（有兴趣的我后⾯可能有浅讲⼀⼿，你们可以浅看⼀⼿）好回归正题，我们来总结⼀下01背包问题。⾸先是⼀个状态表⽰⼆维数组dp[][]，其次就是状态计算，怎么得到这个dp[i][j]，其实也挺简单，刚⼊门就是这么简单。（建议消化⼀下，新知识的接纳需要沉淀）好我们开始下⼀个
与01背包不同 的 是，此问题的物品可以选择⽆限个;状态表⽰跟01背包如出⼀辙，你问为什么，这么类似的题你不⽤类似的状态表⽰么，你还能想出其他的么，想出了当我没说⽽状态计算跟刚刚也⼀样么，不错，⼀样的地⽅是⼀模⼀样的，只需要再添⼀重循环去循化个数就好了。这也是动态规划题⽬经常会遇到的设定，会给出体积限制，数量限制等等限制。代码如下 #include 与上述俩个问题不同的是既不是只能选⼀个也不是⽆限选，多重背包问题中是每个物品有数量限制，只能选⼏个。这就是数量限制了，加嘛，加条件⽽已，谁都会。#include for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k<=s[i];k++){ if(j>=k*v[i]){ dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]); } } } } printf("%d",dp[n][m]); return 0;}欸，为什么这题n3⽅的时间复杂度既然过了，因为这题数值范围⽐较⼩的说（不然你能过？？）三题下来貌似很简单嘛，就很模板化了，接下来继续看 此题与上述三题⼜有点不⼀样了。他将所有物品分成⼏个组，欸每组只能选⼏个。他不关⼼你每个能取⼏个了，他关⼼你每组能取⼏个了。emm稍有变通⼀下，我们刚刚关⼼每个第⼀重循环就去枚举物品个数，那我们现在关系每组，就只需要第⼀组去枚举组数就好了。#include } } } cout< 2023年8月1日发(作者：) 动态规划——背包问题（详解）动态规划是我最早接触的算法，⼀开始⾮常简单，固定模板题，后来愈发愈发难起来了，条件，状态压缩等等，难点主要是，状态怎么表⽰，状态转移⽅程怎么写，这篇⽂章将会从背包五⼤问题详解，希望能帮助到⼤家去类⽐，思考其他动态规划题⽬。⾸先先来看看动态规划的定义：动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的⽅式去解决。动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若⼲个⼦问题（阶段），按顺序求解⼦阶段，前⼀⼦问题的解，为后⼀⼦问题的求解提供了有⽤的信息。在求解任⼀⼦问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各⼦问题，最后⼀个⼦问题就是初始问题的解。看完定义我们开始应⽤了！来看基本的01背包问题，也是最经典的动态规划[ps:建议⽽外开个⽹页去打开题⽬链接，⽤Ctrl+tab⾷⽤更佳]这题所求的是V容积下能够装的物品的最⼤值。很显然有容积的限制有时候你不能全部都装，⼜有体积和价值的不确定性，可能你选⼩体积的反⽽会有更⼤的价值，如果去暴⼒枚举时间复杂度呈指数显然不能ac，那么就需要六⼤算法之⼀动态规划了。明确的⼀点此题是求最⼤值，⽽每个物品⾄多选⼀次，也就是只有选和不选俩个状态。我们可以⼀个⼀个物品去决策这个物品是该选还是不该选，这只需要⼀个max函数就能完成了。现在的问题是如何去定义，怎么去记录这个决策过程。依靠现有的知识能储存多组数据的只有数组了，我们可以先定义⼀个⼆维数组dp[N][N]去记录这个过程。int dp[N][N]; //dp[i][j]表⽰容积为j的背包只装前i个物品可以达到的最⼤价值这也是动态规划的第⼀步，明确数组的含义或者集合的含义。接下来可以⼀个⼀个去决策了，先预知⼀下，肯定需要⼀个for循环去枚举物品，枚举完物品⼜需要⼀个for循环去枚举体积。在选或不选的情况下去择优，更新dp[i][j]，n2的时间复杂度，显然对付这题很容易了。for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; j++) { dp[i][j] = dp[i-1][j]; //⼀开始是都选择不装 if(j>=v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]]+w[i]); //只有物品体积⼤于背包容积了才可以开始决策择优选或不选。 }}那么最终答案就是dp[n][m],在只考虑前n个物品最⼤容积为m的背包可以装的物品的最⼤价值ac代码：#include }可能有⼈了解到可以空间压缩，滚动数组等等，在此先不讲，我们前⾯先讲思维。（有兴趣的我后⾯可能有浅讲⼀⼿，你们可以浅看⼀⼿）好回归正题，我们来总结⼀下01背包问题。⾸先是⼀个状态表⽰⼆维数组dp[][]，其次就是状态计算，怎么得到这个dp[i][j]，其实也挺简单，刚⼊门就是这么简单。（建议消化⼀下，新知识的接纳需要沉淀）好我们开始下⼀个 与01背包不同 的 是，此问题的物品可以选择⽆限个;状态表⽰跟01背包如出⼀辙，你问为什么，这么类似的题你不⽤类似的状态表⽰么，你还能想出其他的么，想出了当我没说⽽状态计算跟刚刚也⼀样么，不错，⼀样的地⽅是⼀模⼀样的，只需要再添⼀重循环去循化个数就好了。这也是动态规划题⽬经常会遇到的设定，会给出体积限制，数量限制等等限制。代码如下 #include 与上述俩个问题不同的是既不是只能选⼀个也不是⽆限选，多重背包问题中是每个物品有数量限制，只能选⼏个。这就是数量限制了，加嘛，加条件⽽已，谁都会。#include for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++){ for(int k=0;k<=s[i];k++){ if(j>=k*v[i]){ dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]); } } } } printf("%d",dp[n][m]); return 0;}欸，为什么这题n3⽅的时间复杂度既然过了，因为这题数值范围⽐较⼩的说（不然你能过？？）三题下来貌似很简单嘛，就很模板化了，接下来继续看 此题与上述三题⼜有点不⼀样了。他将所有物品分成⼏个组，欸每组只能选⼏个。他不关⼼你每个能取⼏个了，他关⼼你每组能取⼏个了。emm稍有变通⼀下，我们刚刚关⼼每个第⼀重循环就去枚举物品个数，那我们现在关系每组，就只需要第⼀组去枚举组数就好了。#include } } } cout<
发布评论