leetcode 刷题 log day 42

【标准的背包问题】有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
eg：weight = [1, 3, 4], value = [15, 20, 30], bagWeight = 3;

• 01背包问题 二维解法
  【思路】按照动规五步分析：
  1. dp[i][j] 的含义：从下标为 [0 - i] 的物品中任取，放进容量为 j 的背包，价值总和最大为多少；
  2. 确定递推公式：不放物品 i 时背包最大价值为：dp[i - 1][j]；放入物品 i：dp[i - 1][ j - weight[i] ]为背包容量为 j - weight[i] 的时候不放物品 i 的价值，放入物品 i，就是 加上物品 i 的价值，即：dp[i - 1][ j - weight[i] ] + value[i]；所以递推公式为：dp[i][j] = Math.max( dp[i - 1][j], dp[i - 1][ j - weight[i] ] + value[i]
  3. dp 数组的初始化，当背包容量为 0 的时候，肯定价值也为 0，即 dp[i][0] = 0，当背包容量大于第一个物品的重量（1）时，那么当背包只放这一个物品时，背包的最大价值就是这个物品的价值，即 dp[0][j] = value[0]（j >= 1）；
  4. 确定遍历顺序：先遍历背包或者先遍历物品都可以，试试就知道都可以做出来；

  function testBagWeightProblem (weight, value, size) {
  	const len = weight.length,
            dp = new Array(len).fill().map(() => Array(size + 1).fill(0));
      
      // 初始化
      for (let j = weight[0]; j <= size; j++) {
      	dp[0][j] = value[0];
      }
  	for (let i = i; i < len; i++) {  // 遍历物品
  		for (let j = 0; j <= size; j++) {  // 遍历背包
  			if (j < weight[i]) dp[i][j] = dp[i - 1][j]
  			else 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(testBagWeightProblem([1, 3, 4], [15, 20, 30], 4))
  };
  test();
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 01背包问题 一维解法（滚动数组）
  【思路】动规五部曲分析：
  1. dp[j] 表示容量为 j 的背包所背的物品价值可以最大为 dp[j]；
  2. 递推公式：不放物品 i 时的最大价值为 dp[j] 相当于二维数组中的 dp[i - 1][j] ，放入物品 i 时，是不放物品 i 时的重量 j - weight[i] 时的最大价值 dp[j - weight[i]] 加上 物品 i 的价值 value[i]，所以递推公式为 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  3. 数组初始化：当背包容量为 0 的时候，价值也为 0，所以 dp[0] = 0；
  4. 确定遍历顺序：二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。倒序遍历是为了保证物品 i 只被放入一次，一旦正序遍历了，那么物品0就会被重复加入多次！所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。倒序遍历本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

  function bagWeightProblem (weight, value, size) {
  	const len = weight.length,
  		  dp = new Array(size + 1).fill(0);
  
  	for (let i = 1; i <= len; i++) {
  		for (let j = size; j >= weight[i - 1]; j--) {
  			dp[j] = Math.max(dp[j], value[i - 1] + dp[j - weight[i - 1]]);
  		}
  	}
  	return dp[size];
  }
  
  function test () {
  	console.log(bagWeightProblem([1, 2, 3], [15, 20, 30], 4));
  }
  
  test();
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

• 416. 分割等和子集
  【思路】这道题意思是找是否有数组的子集加起来等于数组总和的二分之一，也属于背包问题，并且每个元素只能用一次，所以属于 01 背包问题。接下来就是照搬公式，硬往上套！先清楚背包的体积相当于数组总和的二分之一，每个元素的值就是物品的重量和价值。
  1. dp[j] 表示最大可以凑成 j 的子集总和为 dp[j]
  2. 递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  var canPartition = function(nums) {
    const sum = (nums.reduce((p, v) => p + v));
    if (sum & 1) return false;
    
    let dp = new 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;
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

参考代码随想录：https://www.programmercarl.com/