??專欄：每日算法學(xué)習(xí)
??個(gè)人主頁：個(gè)人主頁

1.前提：什么是0-1背包

??情況描述：有n件物品和一個(gè)最多能背重量為w 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。每一件物品其實(shí)只有兩個(gè)狀態(tài)，取或者不取。
舉一個(gè)例子，之后我們將拿這里例子進(jìn)行后續(xù)分析
weight = []1,3,4]
value = [15,20,30]

2.實(shí)現(xiàn)：二維dp講解

??動(dòng)態(tài)規(guī)劃五部曲：
1.（重要）首先搞懂dp[i][j]代表的意思： 代表從0-i個(gè)物品中，取出任意個(gè)，放入容量為j的背包的價(jià)值總和。i表示取的物品，j表示背包容量
2.確定遞推公式：
分為兩個(gè)方向思考價(jià)值：一個(gè)是不放i物品，一個(gè)是放了i物品。
如果容量不滿足：直接將上一個(gè)背包價(jià)值賦值給dp[i][j]
如果容量滿足：
不放i物品價(jià)值，那么dp[i][j]就是未放i物品的價(jià)值，即dp[i-1][j]
放了i物品價(jià)值，那么此時(shí)最大價(jià)值：dp[i][j]應(yīng)該是dp[i-1][j-weight[i]+value[i]]
兩者取最大值比較即可
遞推公式為：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.初始化dp數(shù)組：
如下圖所示：
當(dāng)背包容量為0的時(shí)候，所有價(jià)值為0；當(dāng)i=0時(shí)，只有一個(gè)物品可供選擇，所以物品0行值為15；之后當(dāng)選擇多起來之后，可以根據(jù)遞推公式得出此時(shí)物品的價(jià)值。所以初始化dp[i][0]和dp[0][j]即可滿足初始化條件，供我們后續(xù)計(jì)算物品價(jià)值。同時(shí)對(duì)于其他值，我們給初始化成0，這樣我們?cè)诤罄m(xù)進(jìn)行求最大值的時(shí)候不會(huì)對(duì)我們產(chǎn)生影響

代碼實(shí)現(xiàn)：

   // 創(chuàng)建dp數(shù)組
        int goods = weight.length;  // 獲取物品的數(shù)量
        //這里數(shù)組容量為什么要+1呢？
        //因?yàn)槲覀冇痔砑恿艘粋€(gè)0，容量變成了5，此時(shí)size才為4，求n的時(shí)候，保證不越界，使求的n就是dp[i][n]，加一保證不越界和好使用
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp數(shù)組
        // 創(chuàng)建數(shù)組后，其中默認(rèn)的值就是0
        //為什么這里是以weight[0]作為其實(shí)值呢？，當(dāng)只有一個(gè)物品時(shí)候，
        //要從容量符合的位置開始裝，初始化第一行價(jià)值
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

4.確定遍歷順序： 因?yàn)閐p數(shù)組需要知道之前的物品價(jià)值，才能求得價(jià)值最大值，所以遍歷順序是從前向后。

5.舉例推導(dǎo)： 就以我們上面的例子來進(jìn)行推導(dǎo)：
代碼實(shí)現(xiàn)：二維dp模板

package excrise.算法專訓(xùn).背包問題;

public class 背包問題0_1 {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
        testWeightBagProblem(weight,value,bagSize);
    }

    /**
     * 動(dòng)態(tài)規(guī)劃獲得結(jié)果
     * @param weight  物品的重量
     * @param value   物品的價(jià)值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 創(chuàng)建dp數(shù)組
        int goods = weight.length;  // 獲取物品的數(shù)量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp數(shù)組
        // 創(chuàng)建數(shù)組后，其中默認(rèn)的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp數(shù)組
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    /**
                     * 當(dāng)前背包的容量都沒有當(dāng)前物品i大的時(shí)候，是不放物品i的
                     * 那么前i-1個(gè)物品能放下的最大價(jià)值就是當(dāng)前情況的最大價(jià)值
                     */
                    dp[i][j] = dp[i-1][j];
                } else {
                    /**
                     * 當(dāng)前背包的容量可以放下物品i
                     * 那么此時(shí)分兩種情況：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比較這兩種情況下，哪種背包中物品的最大價(jià)值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp數(shù)組
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

總結(jié)： 對(duì)于背包求價(jià)值那塊，兩層for循環(huán)換位置當(dāng)你有些迷糊時(shí)，要時(shí)刻去回顧dp[i][j]代表的含義是什么，慢慢才能理解進(jìn)去。

3.實(shí)現(xiàn)：一維dp講解（滾動(dòng)數(shù)組）

相對(duì)于二維dp，我們更加常用一維dp來解決背包問題。
1.理解dp{j】的含義： 相對(duì)于二維dp[i][j]，一維dp[j]中的j表示的是二維數(shù)組中的背包容量j，dp[j]表示此時(shí)背包的最大價(jià)值
2.確定地推公式
分為兩個(gè)方向思考價(jià)值：一個(gè)是不放i物品，一個(gè)是放了i物品。
如果容量不滿足：直接將上一個(gè)背包價(jià)值賦值給dp[j]
如果容量滿足：
不放i物品價(jià)值，那么dp[i][j]就是未放i物品的價(jià)值，即dp[j] (dp[j]是滾動(dòng)更新的，所以可以寫成dp[j])
放了i物品價(jià)值，那么此時(shí)最大價(jià)值：dp[j]應(yīng)該是dp[j-weight[i]+value[i]]
兩者取最大值比較即可
遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 滾動(dòng)更新
3.初始化dp數(shù)組
數(shù)組初始化為0，即定義之后就會(huì)默認(rèn)為0；原因在第四步講解
4.遍歷順序
因?yàn)轭}中要求的是，每個(gè)物品只能使用一次。如果從前向后計(jì)算的話，那么同一個(gè)物品會(huì)被使用多次，即放了多次。所以對(duì)于一維數(shù)組來說，只能從后往前進(jìn)行計(jì)算。這樣才滿足同一個(gè)物品使用一次的條件。從后往前的話，因?yàn)槊總€(gè)物品的值初始化時(shí)0，所以保證了只使用一次。
5.舉例推導(dǎo)：
依舊使用上面的例子：

代碼實(shí)現(xiàn)：

package excrise.算法專訓(xùn).背包問題;

public class 背包問題0_1一維數(shù)組 {
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        test(weight, value, bagWight);
    }

    public static void test(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定義dp數(shù)組：dp[j]表示背包容量為j時(shí)，能獲得的最大價(jià)值
        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] + " ");
        }
    }
}

感謝您的閱讀，如果對(duì)您學(xué)習(xí)有幫助，給個(gè)一鍵三連吧！關(guān)注我，每日更新算法學(xué)習(xí)內(nèi)容。文章來源地址http://www.zghlxwxcb.cn/news/detail-407394.html

到了這里，關(guān)于Leetcode動(dòng)態(tài)規(guī)劃篇（0-1背包問題一維和二維dp實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！