快捷導(dǎo)航

C++動(dòng)態(tài)規(guī)劃中關(guān)于背包問題講解

更新時(shí)間：2023年03月15日 10:03:39 作者：清風(fēng)何渡

可能有些讀者有接觸過動(dòng)態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動(dòng)態(tài)規(guī)劃這個(gè)東西，別擔(dān)心，我這篇文章會(huì)為讀者做一個(gè)入門，好讓讀者掌握這個(gè)重要的知識(shí)點(diǎn)

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

背包問題，難點(diǎn)往往在第一步：dp數(shù)組表示什么

分割等和子集問題，較好的方式是：求裝滿背包后最大重量是多少（有點(diǎn)繞哈哈）

這是個(gè)題型：對(duì)于判斷能不能恰好裝滿背包的問題，用dp表示重量，判斷是否最終的dp[m]==m

bool canPartition(int* nums, int numsSize){
    //首先數(shù)組元素求和的sum，若sum%2==1，返回false
    //若sum%2==0，定義m=sum/2，n=numsSize
    //則問題變成了能否裝滿容量為m的背包
    //進(jìn)一步變成了求裝滿容量為m的背包得到的最大價(jià)值量(本題價(jià)值量即為重量)
    //1.dp[j]表示裝滿容量為j的背包能獲得的最大價(jià)值量
    //2.遞推式:dp[j]=fmax(dp[j],dp[j-nums[i]]+nums[i]);
    //3.dp數(shù)組初始化:dp[i]=0;
    //4.遍歷順序:0-1背包順序(滾動(dòng)數(shù)組)
    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;
}

二、目標(biāo)和

求組合數(shù)模板：dp[0]=1;dp[j]+=dp[j-nums[i]];

int findTargetSumWays(int* nums, int numsSize, int target){
    //首先數(shù)組元素求和的sum，若滿足題意，m+(m-target)=sum
    //若(sum+target)%2==1，返回0;
    //若sum<abs(target)，返回0;
    //否則，有m=(sum+target)/2;
    //問題就變成了整數(shù)m可以有多少表達(dá)式表示出
    //進(jìn)一步變成了求裝滿容量為m的背包的最大組合數(shù)
    //1.dp[j]表示裝滿容量為j的背包的最大表達(dá)式的組合數(shù)
    //2.遞推式:
    //組合問題模板:dp[0]=1;dp[j]+=dp[j-nums[i]];
    //3.dp數(shù)組初始化: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];
}

三、一和零

注意二維滾動(dòng)數(shù)組不能寫在同一個(gè)for循環(huán)中，這題背一下

int findMaxForm(char ** strs, int strsSize, int m, int n){
    //本題是二維背包，不過是比一維多了一步而已
    //1.dp[i][j]表示背包容量為i個(gè)0、j個(gè)1時(shí)，最多能裝的物品個(gè)數(shù)
    //2.遞推式:
    //dp[i][j]=fmax(dp[i][j],dp[i-cnt0][j-cnt1]+1);
    //3.dp數(shù)組初始化:
    //dp[i][j]=0;
    //4.遍歷順序:二維滾動(dòng)數(shù)組(注意不能把i和j寫在同一個(gè)for循環(huán)中)
    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背包唯一的區(qū)別在遍歷順序

我們知道01背包內(nèi)嵌的循環(huán)是從大到小遍歷，為了保證每個(gè)物品僅被添加一次。

而完全背包的物品是可以添加多次的，所以要從小到大去遍歷

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];
}

五、排列與組合

組合總數(shù)IV（排列問題）

本題要求的是排列數(shù)（即考慮排列順序）

求排列數(shù)，外層遍歷重量，內(nèi)層遍歷物品，且均為從左到右遍歷

int combinationSum4(int *nums,int n,int m){
    //1.dp[j]表示背包容量為j時(shí)，有多少種方法能使背包被裝滿“
    //2.遞推式:
    //dp[j]+=dp[j-nums[i]];
    //3.初始化:
    //dp[i]=0;dp[0]=1;
    //4.遍歷順序:
    //本題要求的是排列數(shù)（即考慮排列順序）
    //求排列數(shù)，外層遍歷重量，內(nèi)層遍歷物品，且均為從左到右遍歷
    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];
}

零錢兌換（組合問題）

本題要求的是組合數(shù)（即不考慮排列順序）

求組合數(shù)，外層遍歷物品，內(nèi)層遍歷重量，且均為從左到右遍歷

int int coinChange(int* coins, int coinsSize, int amount){
    //1.dp[j]表示背包容量為j時(shí)，有多少種方法能使背包被裝滿“
    //2.遞推式:
    //dp[j]+=dp[j-coins[i]];
    //3.初始化:
    //dp[i]=0;dp[0]=1;
    //4.遍歷順序:
    //本題要求的是組合數(shù)（即不考慮排列順序）
    //求組合數(shù)，外層遍歷物品，內(nèi)層遍歷重量，且均為從左到右遍歷
    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];
}

到此這篇關(guān)于C++動(dòng)態(tài)規(guī)劃中關(guān)于背包問題講解的文章就介紹到這了,更多相關(guān)C++動(dòng)態(tài)規(guī)劃背包內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: