學習目標：

● 01背包問題，你該了解這些！
● 01背包問題，你該了解這些！ 滾動數(shù)組
● 416. 分割等和子集

學習內(nèi)容：● 01背包問題，你該了解這些！

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
視頻講解：https://www.bilibili.com/video/BV1cg411g7Y6

1.確定dp數(shù)組以及下標的含義
i是物品，j是背包容量。
dp[i][j] 表示從下標為[0-i]的物品里任意取，放進容量為j的背包，價值總和最大是多少。
2.遞推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.初始化：
4.確定遍歷順序：都可以，但是先遍歷物品更好理解。

好難啊，比讀不懂題更顯呆

/**
     * 動態(tài)規(guī)劃獲得結果
     * @param weight  物品的重量
     * @param value   物品的價值
     * @param size    背包的容量
     */
function testWeightBagProblem (weight, value, size) {
	// 獲取物品的數(shù)量
    const len = weight.length
    const dp = Array(len).fill().map(()=>Array(size+1).fill(0))
    // 初始化dp數(shù)組
    for(let j=weight[0];j<=size;j++){
        dp[0][j]=value[0]
    }
    for(let i=1;i<len;i++){
        for(let j=1;j<=size;j++){
            if(j<weight[i]){
            /**
                     * 當前背包的容量都沒有當前物品i大的時候，是不放物品i的
                     * 那么前i-1個物品能放下的最大價值就是當前情況的最大價值
              */
                dp[i][j] = dp[i-1][j]
            }else{
             /**
                     * 當前背包的容量可以放下物品i
                     * 那么此時分兩種情況：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比較這兩種情況下，哪種背包中物品的最大價值最大
                     */
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
            }
            
        }
    }
    return dp[len-1][size]
}
function test () {
    console.log(testWeightBagProblem([2, 2 ,3 ,1 ,5, 2], [2 ,3 ,1 ,5 ,4 ,3], 6));
}
test();

學習內(nèi)容：01背包問題，你該了解這些！ 滾動數(shù)組

https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
視頻講解：https://www.bilibili.com/video/BV1BU4y177kY
一維數(shù)組
1.確定dp數(shù)組的定義
在一維dp數(shù)組中，dp[j]表示：容量為j的背包，所背的物品價值可以最大為dp[j]。
2.公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);可以看出相對于二維dp數(shù)組的寫法，就是把dp[i][j]中i的維度去掉了。
3.一維dp數(shù)組如何初始化，初始化為0
4.一維dp數(shù)組遍歷順序：背包遍歷倒序遍歷是為了保證物品i只被放入一次！
為什么二維dp數(shù)組遍歷的時候不用倒序呢？
因為對于二維dp，dp[i][j]都是通過上一層即dp[i - 1][j]計算而來，本層的dp[i][j]并不會被覆蓋！
先遍歷物品嵌套遍歷背包容量
那可不可以先遍歷背包容量嵌套遍歷物品呢？
不可以！
因為一維dp的寫法，背包容量一定是要倒序遍歷，如果遍歷背包容量放在上一層，那么每個dp[j]就只會放入一個物品，即：背包里只放入了一個物品。
倒序遍歷的原因是，本質(zhì)上還是一個對二維數(shù)組的遍歷，并且右下角的值依賴上一層左上角的值，因此需要保證左邊的值仍然是上一層的，從右向左覆蓋。

function testWeightBagProblem (weight, value, size) {
    const len = weight.length
    const dp = Array(size+1).fill(0)
    for(let i=1;i<=len;i++){
        for(let j=size;j>= wight[i - 1];j--){
           dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);       
        }
    }
    return dp[size]
}
function test () {
    console.log(testWeightBagProblem([2, 2 ,3 ,1 ,5, 2], [2 ,3 ,1 ,5 ,4 ,3], 6));
}
test();

學習內(nèi)容：● 416. 分割等和子集

https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
視頻講解：https://www.bilibili.com/video/BV1rt4y1N7jE
1.確定dp數(shù)組以及下標的含義
01背包中，dp[j] 表示： 容量為j的背包，所背的物品價值最大可以為dp[j]。
套到本題，dp[j]表示 背包總容量（所能裝的總重量）是j，放進物品后，背的最大重量為dp[j]。
2.遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.初始化：dp[0]=0
4.遍歷順序：如果使用一維dp數(shù)組，物品遍歷的for循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層for循環(huán)倒序遍歷！文章來源地址http://www.zghlxwxcb.cn/news/detail-792777.html

兩字：不會！

var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));
    if (sum & 1) return false;
    const dp = Array(sum / 2 + 1).fill(0);
    for(let i = 0; i < nums.length; i++) {
        for(let j = sum / 2; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            if (dp[j] === sum / 2) {
                return true;
            }
        }
    }
    return dp[sum / 2] === sum / 2;
};

到了這里，關于第九章 動態(tài)規(guī)劃part04(● 01背包問題，你該了解這些！ ● 01背包問題，你該了解這些！ 滾動數(shù)組 ● 416. 分割等和子集 )的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！