背包問題

說到背包問題大家都會想到使用動規(guī)的方式來求解,那么為什么用動規(guī)呢,dp數(shù)組代表什么呢?初始化是什么,遍歷方式又是什么,這篇文章筆者將詳細講解背包問題的經(jīng)典例題0-1背包問題和完全背包問題的解題方式,希望能幫助到大家

1.暴力方式

有人一提到背包問題就只會使用動態(tài)規(guī)劃來做,那么背包問題假如讓你使用暴力求解該如何解決呢?我們以0-1背包為例,每個物品是不是只有兩種狀態(tài)?放或者不放,我們可以遍歷所有方式,使用回溯來解決問題.

0-1背包問題解決方式(二維數(shù)組)

動規(guī)五部曲

1.明白dp數(shù)組的含義

此處dp[i][j]表示的就是從[0,i]個物品中任選,用容量為j的背包能裝的最大價值.

2.數(shù)組的初始化和遞推公式的理解

遞推公式:

不放物品:其實就是延續(xù)上一層的最大價值即可

dp[i][j] = dp[i-1][j]

放入物品:取上一層的數(shù)據(jù)或者放入這一層的物品加上剩下的容量的最大價值,兩者之間取最大值即可

dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])

初始化數(shù)組:

首先從定義出發(fā)dp[i][0]一定得初始化為0,0容量的背包裝不了東西

由于每一行的數(shù)據(jù)都是由上一行推導(dǎo)產(chǎn)生的,所以第一行的數(shù)據(jù)我們也要進行初始化,i從weight[0]開始初始化就行,因為背包的容量的大于等于第一個物品的容量才能裝的進去它.

3.遍歷順序的理解

這里我們可以感受一下先遍歷背包和先遍歷物品的區(qū)別,其實都可以達到我們的效果,但是先

遍歷物品更好理解

那么為什么兩種遍歷方式都可以解決問題呢?

如下圖所示,因為無論是哪種遍歷方式,我們的dp[i][j]都是由左上角的元素推導(dǎo)出來的,所以無所謂用哪種遍歷順序都可以.

 for(int i = 1;i<goods;i++){
            for (int j = 1; j <= bagSize; j++) {
                if(j<weight[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
                }
            }
        }

4.打印數(shù)組進行查看

0-1背包示例代碼

    public static void func1(int[] weight, int[] value, int bagSize){

        //初始化dp數(shù)組
        int goods = weight.length;
        int[][] dp = new  int[goods][bagSize+1];
        for (int i = weight[0]; i <=bagSize; i++) {
            dp[0][i] = value[0];
        }
        for(int i = 1;i<goods;i++){
            for (int j = 1; j <= bagSize; j++) {
                if(j<weight[i]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
                }
            }
        }
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <=bagSize; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }




    }












//main方法中代碼
        int[] value = {15,20,30};
        int[] weight = {1,3,4};
        int bagSize = 4;
        func1(weight,value,bagSize);

0-1背包問題解決方式(一維數(shù)組)

1.明白dp數(shù)組的含義

這里使用一維數(shù)組滾動覆蓋來代替二維數(shù)組,就類似于將一個矩陣壓成了一行

我們先回顧一下二維數(shù)組的含義dp[i][j]:從[0,i]的物品中,背包容量為j能裝的最大價值

這里的dp[j]就是背包容量為j能裝的最大價值

其實可以發(fā)現(xiàn)如果把dp[i - 1]那一層拷貝到dp[i]上，表達式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

2.遞推公式的理解

我們知道dp[j]可以通過dp[j - weight[i]]推導(dǎo)出來，dp[j - weight[i]]表示容量為j - weight[i]的背包所背的最大價值。

然后遞推公式由兩個選擇,一個是上一層的值和本層的物品價值加上剩余空間價值的較大值

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

3.數(shù)組的初始化

根據(jù)上面的遞推公式,我們知道初始化一定不能初始化成一個大值,因為可能太大了而導(dǎo)致后面的dp[j-weight[i]]+value[i]無法覆蓋他的值,所以我們初始化為0即可

4.遍歷順序的理解

我們先上代碼,后講解原因

我們發(fā)現(xiàn)這里的背包遍歷是從后向前遍歷的,為什么呢,舉個例子

如果是從前向后遍歷

那么dp[1] = dp[1-1]+value[0] = 15

dp[2] = dp[2-1] +value[0]= 30

這不符合我們0-1背包的每件物品只能使用一次的邏輯,因為這里物品1被放入了兩次

而我們從后向前遍歷就可以避免這個問題

dp[4] = dp[3]+value[0];

dp[3] = dp[2]+value[0];

...這里就不會存在重復(fù)計算問題

為什么上面二維數(shù)組的遍歷不需要倒序呢?

因為二維數(shù)組的dp[i][j]是由上一層的元素推導(dǎo)出來,不會影響本層的元素

以為數(shù)組的遍歷順序只能是先遍歷物品,再遍歷背包!!!

我們還是舉個例子來說明(一維數(shù)組,我們以二維數(shù)組的形式畫出來),我們就會發(fā)現(xiàn),如果用容量來遍歷物品的話,其實就是每個容量的背包只取得了一個物品,與答案相悖

for(int i = 0; i < weight.size(); i++) { // 遍歷物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍歷背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

5.打印數(shù)組進行查看

示例代碼?

   public static void func2(int[] weight, int[] value, int bagWeight) {
        int wLen = weight.length;
        //定義dp數(shù)組：dp[j]表示背包容量為j時，能獲得的最大價值
        int[] dp = new int[bagWeight + 1];
        //遍歷順序：先遍歷物品，再遍歷背包容量
        for (int i = 0; i < wLen; i++) {
            for (int j = bagWeight; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp數(shù)組
        for (int j = 0; j <= bagWeight; j++) {
            System.out.print(dp[j] + " ");
        }
    }
}

LeetCode T416 等和子集問題

題目鏈接:416. 分割等和子集 - 力扣（LeetCode）

題目思路:

利用上述思路,這里的背包容量是數(shù)組之和的一半,重量和價值數(shù)組都等于源數(shù)組,上面給出一定的剪枝,假如出現(xiàn)奇數(shù)就直接返回false,出現(xiàn)只有一個元素也直接返回false,下面我給出解題代碼.

題目代碼:文章來源地址http://www.zghlxwxcb.cn/news/detail-740550.html

class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length == 1){
            return false;
        }
        int sum = 0;
        for(int i:nums){
            sum += i;
        }
        if(sum % 2 == 1){
            return false;
        }
        int bagSize = sum/2;
        int[] dp = new int[bagSize+1];
        //初始化均為0
        for(int i = 0;i<nums.length;i++){
            for(int j = bagSize;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[bagSize] == bagSize){
            return true;
        }
       return false;

    }
}

到了這里，關(guān)于代碼隨想錄 Day35 動態(tài)規(guī)劃04 01背包問題和完全背包問題 LeetCode T416 分割等和子集的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！