宁波网站推广优化公司怎么样,做网站优势,中小微企业和个体工商户,付费小说网站怎么做文章目录 1、动规思路简介2、模版题#xff1a;01背包第一问第二问优化 3、分割等和子集4、目标和5、最后一块石头的重量Ⅱ 背包问题需要读者先明白动态规划是什么#xff0c;理解动规的思路#xff0c;并不能给刚接触动规的人学习。所以最好是看了之前的动规博客#xff0… 文章目录 1、动规思路简介2、模版题01背包第一问第二问优化 3、分割等和子集4、目标和5、最后一块石头的重量Ⅱ 背包问题需要读者先明白动态规划是什么理解动规的思路并不能给刚接触动规的人学习。所以最好是看了之前的动规博客才能看背包问题的所有博客或者你本人就已经懂得动规了。 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]也就出来了此时的顺序就是从左到右。还有别的顺序要依据前面的分析来决定。
返回值要看题目要求。 背包问题有很多种分类此篇是关于01背包问题的。背包问题在写完代码都需要再做优化。所以比起之前的动规算法博客背包问题的几篇博客都在最后加上一步优化。但优化方法只在模版题写其它不写了。 2、模版题01背包
DP41 【模板】01背包 第一问
先定dp[i]为从前i个物品选选出最大价值的这个其实是不行的如果要选第i个物品就需要看看背包满没满但是现在的状态没法表示体积所以不行。那就用二维数组dp[i][j]表示从前i个物品中挑选总体积不超过j所有选法中能选出的最大价值。
状态转移方程。根据最后一步来分析。我们可以选择第i个物品也可以不选。如果不选就是在0到i- 1中选这个的结果放在dp[i -1][j]中如果选择i位置的元素也就是体积加上vi那为了不超过背包就得选择dp[i - 1][j - vi]位置的值加上wi这个情况还有考虑可能vi大于j了所以j - vi需要 0。所以dp[i][j] max(dp[i - 1][j - 1], dp[i - 1][j - vi] wi)。
初始化要加上一行一列里面的值全都为0。返回值是最大值。
第二问
在第一问基础上来做改动。之前的dp[i][j]要从不超过j改成正好等于j。状态转移方程中有可能选上一个后仍然不够j。如果不选第i个物品那么就是dp[i - 1][j]意思是在前i - 1个物品中选体积等于j的最大价值但有可能是达不到j的我们先定义dp[i][j] -1来表示没有这种情况也就是前i个物品中没有能达到体积为j的选法。如果dp[i - 1][j]是-1那么不选i位置的物品还是体积达不到j所以不选的话就不用考虑了。选第i个物品的话就要先看看dp[i - 1][j - vi]存不存在不等于-1也就是说前i - 1个位置正好达到了j - vi的体积那么加上第i个物品就可行了。
初始化。新增行列第一列整体都是0第一行其余都是-1。
#include iostream
#include cstring
using namespace std;const int N 1010;int n, V, v[N], w[N];
int dp[N][N];int main()
{cin n V;for(int i 1; i n; i){cin v[i] w[i];}for(int i 1; i n; i){for(int j 1; j V; 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]);}}cout dp[n][V] endl;//第一问memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[0][j] -1;for(int i 1; i n; i){for(int j 1; j V; j){dp[i][j] dp[i - 1][j];if(j v[i] dp[i - 1][j - v[i]] ! -1) dp[i][j] max(dp[i][j], dp[i - 1][j - v[i]] w[i]);}}cout (dp[n][V] -1 ? 0 : dp[n][V]) endl;return 0;
}优化
数组很大用滚动数组的思路来优化。仔细看一下分析dp[i][j]由dp[i - 1][j]和dp[i - 1][j - vi]来决定也就是这一行的一个元素由上一行的两个元素来决定和其它行都没有关系那么我们仅需要两行其实就是可以完成dp表的填写根据第一行填完第二行后第一行作为原先的第二行第二行作为新的第二行继续更新数据。这就是滚动数组。但还可以减少空间。只用一行来进行操作。dp[j]由dp[j]和dp[j - vi]来决定然后更新dp[j]用一行的话填表顺序就不能是从左到右因为dp[j - vi]会把dp[j - vi]给换掉所以填表顺序应当是从右到左才能保证每个值都正确更新。
#include cstdio
#include iostream
#include cstring
using namespace std;const int N 1010;int n, V, v[N], w[N];
int dp[N];int main()
{cin n V;for(int i 1; i n; i){cin v[i] w[i];}for(int i 1; i n; i){for(int j V; j v[i]; j--)//原本是j 1在下面判断但其实可以直接放在for括号里减少循环次数{dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[V] endl;//第一问memset(dp, 0, sizeof(dp));for(int j 1; j V; j) dp[j] -1;for(int i 1; i n; i){for(int j V; j v[i]; j--){if(dp[j - v[i]] ! -1)dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout (dp[V] -1 ? 0 : dp[V]) endl;return 0;
}3、分割等和子集
416. 分割等和子集 可以转化成挑选一个数来达到是整体数组和的一半这个条件。并且其实就是从前i个数中选所有的选法中能否凑齐j这个数类型为boolj就是sum / 2。
状态转移方程。如果不选i那就看dp[i - 1][j]如果选i那就是拿前面值加上i位置的值假设前面的值是numi那么这个位置应当在j - numi位置但是j - numi必须存在才行。
初始化新增一行一列第一列都是true第一行其余位置都是false。
返回值是dp[n][sum / 2]。 bool canPartition(vectorint nums) {int n nums.size(), sum 0;for(auto x : nums) sum x;if(sum % 2) return false;int aim sum / 2;vectorvectorbool dp(n 1, vectorbool(aim 1));for(int i 0; i n; i) dp[i][0] true;for(int i 1; i n; i){for(int j 1; j aim; j){dp[i][j] dp[i - 1][j];if(j nums[i - 1])dp[i][j] dp[i][j] || dp[i - 1][j - nums[i - 1]];}}return dp[n][aim];}但是这种做法实在不妥按照滚动数组优化一下。 bool canPartition(vectorint nums) {int n nums.size(), sum 0;for(auto x : nums) sum x;if(sum % 2) return false;int aim sum / 2;vectorbool dp(aim 1);dp[0] true;for(int i 1; i n; i){for(int j aim; j nums[i - 1]; j--){dp[j] dp[j] || dp[j - nums[i - 1]];}}return dp[aim];}4、目标和
494. 目标和 根据题目这些数字会被分为正数和负数假设正数是a负数绝对值是b也就是说a b suma - b target所以a (t s) / 2此时b就不见了。那么只用看a也就是说选一些数和正好是a有多少种选法就是答案。dp[i][j]就表示从前i个数中选总和正好等于i一共有多少种选法。
状态转移方程。如果选i那么就看dp[i - 1][j nums[i]]因为是方法个数所以不需要nums[i]不选择i的话就看dp[i - 1][j]。
初始化时新增行列都是0除了dp[0][0]是1。
返回值是最后一个值。优化部分直接写到代码上。 int findTargetSumWays(vectorint nums, int target) {int sum 0;for(auto x: nums) sum x;int aim (sum target) / 2;if(aim 0 || (sum target) % 2) return 0;int n nums.size();vectorint dp(aim 1);dp[0] 1;for(int i 1; i n; i){for(int j aim; j nums[i - 1]; j--){dp[j] dp[j - nums[i - 1]];}}return dp[aim];}5、最后一块石头的重量Ⅱ
1049. 最后一块石头的重量 II 分析题目。每次拿到两个数字按照题目去操作其实就相当于一个正数和一个负数相加得到一个值是0就都没了那么元素多了的话就和上一题相似一堆正数和一堆负数之间的运算。假设正数是a负数的绝对值和是b那么a b sum求最小的a - b的值。从sum角度看一个数字可以分成两个数字相加如果这两个数字越接近sum的一半那么就差值就越小。所以最终这个问题就转换成在数组中选择一些数让这些数的和尽可能地接近sum / 2。
让dp[i][j]表示从前i个数中选总和不超过j此时的最大和。这个j就是sum / 2。如果选i那就是dp[i - 1][j - nums[i]] nums[i]如果不选i那就是dp[i - 1][j]然后选出最大值。
初始化新增行列都是0就可。
返回值返回sum - 2* dp[n][sum / 2]。优化直接写出来。 int lastStoneWeightII(vectorint stones) {int sum 0;for(auto x : stones) sum x;int n stones.size(), m sum / 2;vectorint dp(m 1);for(int i 1; i n; i){for(int j m; j stones[i - 1]; j--){dp[j] max(dp[j], dp[j - stones[i - 1]] stones[i - 1]);}}return sum - 2 * dp[m];}结束。
