本篇内容主要讲解“C++动态规划中关于背包问题怎么解决”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“C++动态规划中关于背包问题怎么解决”吧!
一、分割等和子集-最后一块石头的重量II
背包问题,难点往往在第一步:dp数组表示什么
分割等和子集问题,较好的方式是:求装满背包后最大重量是多少(有点绕哈哈)
这是个题型:对于判断能不能恰好装满背包的问题,用dp表示重量,判断是否最终的dp[m]==m
bool canPartition(int* nums, int numsSize){ //首先数组元素求和的sum,若sum%2==1,返回false //若sum%2==0,定义m=sum/2,n=numsSize //则问题变成了能否装满容量为m的背包 //进一步变成了求装满容量为m的背包得到的最大价值量(本题价值量即为重量) //1.dp[j]表示装满容量为j的背包能获得的最大价值量 //2.递推式:dp[j]=fmax(dp[j],dp[j-nums[i]]+nums[i]); //3.dp数组初始化:dp[i]=0; //4.遍历顺序:0-1背包顺序(滚动数组) int sum=0; for(int i=0;i<numsSize;i++) sum+=nums[i]; if(sum%2==1) return false; int m=sum/2,n=numsSize; int dp[m+1]; for(int j=0;j<=m;j++) dp[j]=0; for(int i=0;i<n;i++){ for(int j=m;j>=nums[i];j--) dp[j]=fmax(dp[j],dp[j-nums[i]]+nums[i]); } if(dp[m]==m) return true; else return false; }
二、目标和
求组合数模板:dp[0]=1;dp[j]+=dp[j-nums[i]];
int findTargetSumWays(int* nums, int numsSize, int target){ //首先数组元素求和的sum,若满足题意,m+(m-target)=sum //若(sum+target)%2==1,返回0; //若sum<abs(target),返回0; //否则,有m=(sum+target)/2; //问题就变成了整数m可以有多少表达式表示出 //进一步变成了求装满容量为m的背包的最大组合数 //1.dp[j]表示装满容量为j的背包的最大表达式的组合数 //2.递推式: //组合问题模板:dp[0]=1;dp[j]+=dp[j-nums[i]]; //3.dp数组初始化:dp[i]=0;dp[0]=1; int sum=0; for(int i=0;i<numsSize;i++) sum+=nums[i]; if(sum<abs(target)||(sum+target)%2==1) return 0; int m=(sum+target)/2,n=numsSize; int dp[m+1]; for(int i=1;i<=m;i++) dp[i]=0; dp[0]=1; for(int i=0;i<n;i++){ for(int j=m;j>=nums[i];j--) dp[j]+=dp[j-nums[i]]; } return dp[m]; }
三、一和零
注意二维滚动数组不能写在同一个for循环中,这题背一下
int findMaxForm(char ** strs, int strsSize, int m, int n){ //本题是二维背包,不过是比一维多了一步而已 //1.dp[i][j]表示背包容量为i个0、j个1时,最多能装的物品个数 //2.递推式: //dp[i][j]=fmax(dp[i][j],dp[i-cnt0][j-cnt1]+1); //3.dp数组初始化: //dp[i][j]=0; //4.遍历顺序:二维滚动数组(注意不能把i和j写在同一个for循环中) int dp[m+1][n+1]; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++) dp[i][j]=0; } for(int k=0;k<strsSize;k++){ int cnt0=0,cnt1=0; int len=strlen(strs[k]); for(int i=0;i<len;i++){ if(strs[k][i]=='0') cnt0++; else cnt1++; } for(int i=m;i>=cnt0;i--){ for(int j=n;j>=cnt1;j--){ dp[i][j]=fmax(dp[i][j],dp[i-cnt0][j-cnt1]+1); } } } return dp[m][n]; }
四、零钱兑换II
多重背包和0-1背包唯一的区别在遍历顺序
我们知道01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的,所以要从小到大去遍历
int change(int amount, int* coins, int coinsSize){ int m=amount,n=coinsSize; int dp[m+1]; for(int i=1;i<=m;i++) dp[i]=0; dp[0]=1; for(int i=0;i<n;i++){ for(int j=coins[i];j<=m;j++) dp[j]+=dp[j-coins[i]]; } return dp[m]; }
五、排列与组合
组合总数IV(排列问题)
本题要求的是排列数(即考虑排列顺序)
求排列数,外层遍历重量,内层遍历物品,且均为从左到右遍历
int combinationSum4(int *nums,int n,int m){ //1.dp[j]表示背包容量为j时,有多少种方法能使背包被装满“ //2.递推式: //dp[j]+=dp[j-nums[i]]; //3.初始化: //dp[i]=0;dp[0]=1; //4.遍历顺序: //本题要求的是排列数(即考虑排列顺序) //求排列数,外层遍历重量,内层遍历物品,且均为从左到右遍历 int dp[m+1]; for(int i=1;i<=m;i++) dp[i]=0; dp[0]=1; for(int j=0;j<=m;j++){ for(int i=0;i<n;i++){ if(j>=nums[i]&&dp[j]<INT_MAX-dp[j-nums[i]]) dp[j]+=dp[j-nums[i]]; } } return dp[m]; }
零钱兑换(组合问题)
本题要求的是组合数(即不考虑排列顺序)
求组合数,外层遍历物品,内层遍历重量,且均为从左到右遍历
int int coinChange(int* coins, int coinsSize, int amount){ //1.dp[j]表示背包容量为j时,有多少种方法能使背包被装满“ //2.递推式: //dp[j]+=dp[j-coins[i]]; //3.初始化: //dp[i]=0;dp[0]=1; //4.遍历顺序: //本题要求的是组合数(即不考虑排列顺序) //求组合数,外层遍历物品,内层遍历重量,且均为从左到右遍历 int m=amount,n=coinsSize; int dp[m+1]; for(int i=1;i<=m;i++) dp[i]=0; dp[0]=1; for(int i=0;i<n;i++){ for(int j=coins[i];j<=m;j++) dp[j]+=dp[j-coins[i]]; } return dp[m]; }