C++动态规划中关于背包问题讲解

目录

• 一、分割等和子集-最后一块石头的重量II
• 二、目标和
• 三、一和零
• 四、零钱兑换II
• 五、排列与组合
• 组合总数IV（排列问题）
• 零钱兑换（组合问题）

一、分割等和子集-最后一块石头的重量II

背包问题，难点往往在第一步：dp数组表示什么

分割等和子集问题，较好的方式是：求装满背包后最大重量是多少（有点绕哈哈）

这是个题型：对于判断能不能恰好装满背包的问题，用dp表示重量，判断是否最终的dp[m]==m

bool canPartition(int* nums, int numsSize){
    //首先数组元素求和的sum，若sum%2==1，返回false
  js  //若sum%2==0，定义m=sum/2，n=numsSize
www.devze.com    //则问题变成了能否装满容量为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++)
       开发者_Go入门     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时，有多少种方法能使背包被装满“
    www.devze.com//2.递推式:
    //dp[j]+=dp[j-coins[i]];js
    //3.初始化:
    //dp[i]=0;dp[0]=1;
    //4.遍历顺序:
    //本题要求的是组合数（即不考虑排列顺序）
    //求组合数，外层遍历物品，内层遍历重量，且均为从左到右遍历
    int m=amount,n=coinsSize;
    int dp[m+www.devze.com1];
    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];
}

到此这篇关于C++动态规划中关于背包问题讲解的文章就介绍到这了,更多相关C++动态规划背包内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！