01背包理論基礎(chǔ)

解法一：
暴力解法：每種物品有取/不取兩種狀態(tài)。
時間復(fù)雜度：O(2ⁿ)
解法二：
動態(tài)規(guī)劃: 二維數(shù)組

1. dp[i][j]含義：[0,i]物品，任取，背包容量為j，能取得的最大價值
2. 遞推公式：兩種方式推到至下一步。
   • 不放物品i：由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]。(其實就是當(dāng)物品i的重量大于背包j的重量時，物品i無法放進背包中，所以被背包內(nèi)的價值依然和前面相同。)

• 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值

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

3. 初始化
   觀察可知：下一步數(shù)值由上一行的數(shù)值得到；因此，i=0，一定要初始化

   
   
   image.png
   
   

   dp[i][0]，均為0，因為背包容量為0
   dp[0][j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價值。

4. 確定遍歷順序
   同樣根據(jù)上圖，可知，先遍歷背包，或先遍歷物品均可

// weight 物品重量
// value 物品價值
// volumn 背包容量
function maxValue(weight, value, volumn) {
  let n = weight.length; //物品個數(shù)
  let dp = new Array(n).fill(0).map((ele) => {
    return new Array(volumn + 1).fill(0);
  });

  // 初始化
  for (let j = 0; j <= volumn; j++) {
    dp[0][j] = value[0];
  }
  for (let i = 0; i < n; i++) {
    dp[i][0] = 0;
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= volumn; j++) {
      if (j - weight[i] < 0) {
        dp[i][j] = dp[i - 1][j];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
      }
    }
  }

  // 打印
  for (let i = 0; i < n; i++) {
    let str = "";
    for (let j = 0; j <= volumn; j++) {
      str += dp[i][j] + " ";
    }
    console.log(str);
  }

  return dp[i][j]
}

// test
maxValue([1, 3, 4], [15, 20, 30], 4);
// 結(jié)果
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35

解法三：動態(tài)規(guī)劃：一維dp數(shù)組

1. dp數(shù)組含義dp[i]：容量為i的背包的最大價值
2. 遞推公式：dp[i]=max( dp[i],dp[i-Wi-1]+Vi)
3. 初始化：dp均為0
4. 遍歷順序：只能先物品后背包，背包為倒序
   倒序原因：dp數(shù)組是重復(fù)利用的。且因為在二維數(shù)組中，dp[i][j]是依據(jù)上一行的左邊推導(dǎo)出來的，所以一維數(shù)組應(yīng)該從右向左（倒序）遍歷。倒序才能真的拿到原來左側(cè)的舊值

function maxValue2(weight, value, volumn) {
  let n = weight.length; //物品數(shù)量
  let dp = new Array(volumn + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let j = volumn; j >= 0; j--) {
      if (j - weight[i] >= 0) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
      }
    }
  }
  console.log(dp); //[ 0, 15, 15, 20, 35 ]
  return dp[volumn]
}
maxValue2([1, 3, 4], [15, 20, 30], 4);

分割等和求子集

力扣題目
本質(zhì)：01背包的應(yīng)用。將子集看作是物品，物品的重量與價值均為元素的值，看其是否能找到dp[num]===target/2

遞推公式：
dp[j]=max(dp[j],dp[j-num[i]]+num[i])
初始化：
dp均為0。

var canPartition = function(nums) {
    let sum = nums.reduce((p, c) => {
    return p + c;
  }, 0);

  if (sum % 2 !== 0) {
    return false;
  }

  let volumn = sum / 2; //背包容量
  let n = nums.length; //物品個數(shù)
  let dp = new Array(volumn + 1).fill(0);//初始化

  for (let i = 0; i < n; i++) {
    for (let j = volumn; j >= 0; j--) {
      if (j - nums[i] >= 0) {
        dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
      }
    }
  }

  return dp[volumn] === sum / 2;
};

目標(biāo)和

力扣題目鏈接
分析：背包問題的應(yīng)用
其實是求裝滿有幾種方法，是一個組合問題。
轉(zhuǎn)換為背包問題：
假設(shè)加法的總和為x，那么減法對應(yīng)的總和就是sum - x。
所以我們要求的是 x - (sum - x) = target
x = (target + sum) / 2
此時問題就轉(zhuǎn)化為，裝滿容量為x的背包，有幾種方法。

1. dp數(shù)組含義：裝滿容量為j（包括j）的包，有dp[j]種方法
2. 遞推公式：dp[j] += dp[j - nums[i]]
   (補充：所以求組合類問題的公式，都是類似這種遞推公式）
3. 初始化：
   dp[0]=1
   例如：需帶入例子。數(shù)組[0] ，target = 0，那么 bagSize = (target + sum) / 2 = 0

var findTargetSumWays = function(nums, target) {
    let sum=nums.reduce((p,c)=>p+c)
    if(Math.abs(target) > sum) {
        return 0;
    }

    if((target + sum) % 2) {
        return 0;
    }
    
    let bagSize= Math.floor((sum+target)/2)
    let dp=new Array(bagSize+1).fill(0)
    dp[0]=1

    for(let i=0;i<nums.length;i++){
        for(let j=bagSize;j>=nums[i];j--){
            dp[j] += dp[j-nums[i]]
        }
    }
    return dp[bagSize]
};