北京网站设计服务,app手机软件开发,中铁门户网登录,济宁网站建设是什么意思文章目录 1、动规思路简介2、一和零3、盈利计划 背包问题需要读者先明白动态规划是什么#xff0c;理解动规的思路#xff0c;并不能给刚接触动规的人学习。所以最好是看了之前的动规博客#xff0c;以及两个背包博客#xff0c;或者你本人就已经懂得动规了。 1、动规思路简… 文章目录 1、动规思路简介2、一和零3、盈利计划 背包问题需要读者先明白动态规划是什么理解动规的思路并不能给刚接触动规的人学习。所以最好是看了之前的动规博客以及两个背包博客或者你本人就已经懂得动规了。 1、动规思路简介
动规的思路有五个步骤且最好画图来理解细节不要怕麻烦。当你开始画图仔细阅读题时学习中的沉浸感就体验到了。 状态表示 状态转移方程 初始化 填表顺序 返回值 动规一般会先创建一个数组名字为dp这个数组也叫dp表。通过一些操作把dp表填满其中一个值就是答案。dp数组的每一个元素都表明一种状态我们的第一步就是先确定状态。
状态的确定可能通过题目要求来得知可能通过经验 题目要求来得知可能在分析过程中发现的重复子问题来确定状态。还有别的方法来确定状态但都大同小异明白了动规这些思路也会随之产生。状态的确定就是打算让dp[i]表示什么这是最重要的一步。状态表示通常用某个位置为结尾或者起点来确定。
状态转移方程就是dp[i]等于什么状态转移方程就是什么。像斐波那契数列dp[i] dp[i - 1] dp[i - 2]。这是最难的一步。一开始可能状态表示不正确但不要紧大胆制定状态如果没法推出转移方程没法得到结果那这个状态表示就是错误的。所以状态表示和状态转移方程是相辅相成的可以帮你检查自己的思路。
要确定方程就从最近的一步来划分问题。
初始化就是要填表保证其不越界。像第一段所说动规就是要填表。比如斐波那契数列如果要填dp[1]那么我们可能需要dp[0]和dp[-1]这就出现越界了所以为了防止越界一开始就固定好前两个值那么第三个值就是前两个值之和也不会出现越界。初始化的方式不止这一点有些问题假使一个位置是由前面2个位置得到的我们初始化最一开始两个位置然后写代码会发现不够高效这时候就需要设置一个虚拟节点一维数组的话就是在数组0位置处左边再填一个位置整个dp数组的元素个数也1让原先的dp[0]变为现在的dp[1]二维数组则是要填一列和一行设置好这一行一列的所有值原先数组的第一列第一行就可以通过新填的来初始化这个初始化方法在下面的题解中慢慢领会。
第二种初始化方法的注意事项就是如何初始化虚拟节点的数值来保证填表的结果是正确的以及新表和旧表的映射关系的维护也就是下标的变化。
填表顺序。填当前状态的时候所需要的状态应当已经计算过了。还是斐波那契数列填dp[4]的时候dp[3]和dp[2]应当都已经计算好了那么dp[4]也就出来了此时的顺序就是从左到右。还有别的顺序要依据前面的分析来决定。
返回值要看题目要求。 背包问题有很多种分类此篇是关于二维费用背包问题的优化代码的方法在之前的两篇背包博客的模板题中此篇就不写了。 2、一和零
474. 一和零 二维费用的背包问题就是原先的背包问题再加一个考虑因素比如要考虑体积和重量。二维也有01和完全背包这道题是二维01背包问题。
01背包中dp[i][j]表示从前i个物品中挑选总体积不超过j最大价值的选法。这道题就要再加一维变成dp[i][j][k]从前i个字符串中挑选字符0的个数不超过j字符1的个数不超过k最大长度的选法。
状态转移方程。其实还是一样的分析。最后一个位置的字符串如果不选i那么就看dp[i - 1][j][k]如果选ii这个字符串有a个0 1以及b个1所以就看dp[i - 1][j - a][k - b]然后 1并且要求j - a 0k - b 0两个值取max。
初始化时i为0则dp[0][j][k]全为0。返回值因为要从整个字符串数组中挑选而不是其中某一个最大值所以返回值是最后一个值。 int findMaxForm(vectorstring strs, int m, int n) {int len strs.size();vectorvectorvectorint dp(len 1, vectorvectorint(m 1, vectorint(n 1)));for(int i 1; i len; i){int a 0, b 0;for(auto ch : strs[i - 1]){if(ch 0) a;else b;}for(int j 0; j m; j){for(int k 0; k n; k){dp[i][j][k] dp[i - 1][j][k];if(j a k b)dp[i][j][k] max(dp[i][j][k], dp[i - 1][j - a][k - b] 1);}}}return dp[len][m][n];}但肯定不能这样写做优化。去掉i这一维j和k从大到小循环。 int findMaxForm(vectorstring strs, int m, int n) {int len strs.size();vectorvectorint dp(m 1, vectorint(n 1));for(int i 1; i len; i){int a 0, b 0;for(auto ch : strs[i - 1]){if(ch 0) a;else b;}for(int j m; j a; j--){for(int k n; k b; k--){dp[j][k] max(dp[j][k], dp[j - a][k - b] 1);}}}return dp[m][n];}3、盈利计划
879. 盈利计划 给了n和minProFitgroup和profit数组挑选几个人做某一份工作人数不能超过n并且利润也就是profit数组里的被挑选的数要 minProFit选group中第几个元素利润就是profit数组中第几个元素。每个工作只能选一个所以就是01背包问题。
让dp[i][j][k]表示从前i个工作中挑选总人数不超过j总利润至少为k总共的选法。
状态转移方程。我们当然还是以最后一个位置i来分析。选择第i个工作那就看dp[i - 1][j][k]如果选i那么按照上一个题就是dp[i - 1][j - g[i]]k部分由于是至少思路就不一样如果p[i]小于那么就正常地看[k - p[i]]位置如果p[i]大于k就不能选择k - p[i]的位置了因为数组下标不能为负数所以这样写max(0, k - p[i])如果p[i]更大那么保证前面至少为0就行。然后这两个数相加。
初始化时dp[0][j][0] 1。填表顺序要保证i从小到大即可。返回值是最后一个值。 int profitableSchemes(int n, int m, vectorint g, vectorint p) {const int MOD 1e9 7;int len g.size();vectorvectorint dp(n 1, vectorint(m 1));for(int j 0; j n; j) dp[j][0] 1;for(int i 1; i len; i){for(int j n; j g[i - 1]; j--){for(int k m; k 0; k--){dp[j][k] dp[j - g[i - 1]][max(0, k - p[i - 1])];dp[j][k] % MOD;}}}return dp[n][m];}结束。
