代码随想录day42【动态规划】0-1背包问题 分割等和求子集 目标和

01背包理论基础

解法一：
暴力解法：每种物品有取/不取两种状态。
时间复杂度：O(2ⁿ)
解法二：
动态规划: 二维数组

1. dp[i][j]含义：[0,i]物品，任取，背包容量为j，能取得的最大价值
2. 递推公式：两种方式推到至下一步。
   • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品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. 初始化
   观察可知：下一步数值由上一行的数值得到；因此，i=0，一定要初始化

   
   
   image.png
   
   

   dp[i][0]，均为0，因为背包容量为0
   dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

4. 确定遍历顺序
   同样根据上图，可知，先遍历背包，或先遍历物品均可

// weight 物品重量
// value 物品价值
// volumn 背包容量
function maxValue(weight, value, volumn) {
  let n = weight.length; //物品个数
  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);
// 结果
// 0 15 15 15 15
// 0 15 15 20 35
// 0 15 15 20 35

解法三：动态规划：一维dp数组

1. dp数组含义dp[i]：容量为i的背包的最大价值
2. 递推公式：dp[i]=max( dp[i],dp[i-Wi-1]+Vi)
3. 初始化：dp均为0
4. 遍历顺序：只能先物品后背包，背包为倒序
   倒序原因：dp数组是重复利用的。且因为在二维数组中，dp[i][j]是依据上一行的左边推导出来的，所以一维数组应该从右向左（倒序）遍历。倒序才能真的拿到原来左侧的旧值

function maxValue2(weight, value, volumn) {
  let n = weight.length; //物品数量
  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);

分割等和求子集

力扣题目
本质：01背包的应用。将子集看作是物品，物品的重量与价值均为元素的值，看其是否能找到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; //物品个数
  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;
};

目标和

力扣题目链接
分析：背包问题的应用
其实是求装满有几种方法，是一个组合问题。
转换为背包问题：
假设加法的总和为x，那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) = target
x = (target + sum) / 2
此时问题就转化为，装满容量为x的背包，有几种方法。

1. dp数组含义：装满容量为j（包括j）的包，有dp[j]种方法
2. 递推公式：dp[j] += dp[j - nums[i]]
   (补充：所以求组合类问题的公式，都是类似这种递推公式）
3. 初始化：
   dp[0]=1
   例如：需带入例子。数组[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]
};