01背包与完全背包问题

动态规划是刷题过程中的常见算法，有难有易，简单的如斐波那契数列问题很容易找到规律，难一些的就很容易钻牛角尖了，而背包问题又是动态规划的一个典型问题，这里就拿比较典型的01背包与完全背包问题做一下记录。

01背包问题

01背包问题题目要求

• 有N件物品和一个容量为V的背包
• 第i件物品的体积是Vi，其价值是Wi
• 每件物品只能使用一次
• 要求物品体积不超过背包容量且价值最大

理清楚思路就容易理解了。用到了两层for循环，外层是依次循环每个物品，内层是背包容积，依次去计算当前容积下的最大价值，后续的计算可以依赖前边的计算，完成算法。

/**
 * @description 0-1背包问题
 * @param {number} n 物品数量
 * @param {number} v 背包的容积
 * @param {number[]} w 物品价值数组,索引为0的物品价值为0
 * @param {number[]} c 物品体积数组,索引为0的物品价值为0
 */
function zeroOneBag(n, v, w, c){
  // w和c都是索引为0的值也是0，因为没有第0件物品
  // 所以我们生成二维数组的时候也用到了n+1，保证索引对应
  // 需要注意的是，不要用这种方式生成二维数组：
  // let dp = new Array(n+1).fill(new Array(v+1).fill(0))
  // 因为数组是引用类型，会导致修改一个其他的也受影响
  let dp = []
  for(let i = 0; i < n+1; i++){
      dp.push(new Array(v+1).fill(0))
  }
  for(let i=1; i<n+1; i++){
    for(let j=1; j<v+1; j++){
      // 如果容积小于物品体积那么放不进去
      if(j < c[i]){
        // 当前的最大值就不不放入这个物品的值
        dp[i][j] = dp[i-1][j]
      }else{
        // 如果容积大于物品体积，则考虑取较大值：
        // 1.不放当前物品 || 2.放当前物品+减去当前物品剩余容积的最大价值
        dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-c[i]] + w[i])
      }
    }
  }
  return dp[n][v]
}

但是这样用到了一个二维数组，空间复杂度较高，有没有可能通过一维数组实现呢？

01背包问题空间复杂度优化

关键点只有一个，容积要逆序循环保证不会重复使用物品

/**
 * @description 0-1背包问题
 * @param {number} n 物品数量
 * @param {number} v 背包的容积
 * @param {number[]} w 物品价值数组,索引为0的物品价值为0
 * @param {number[]} c 物品体积数组,索引为0的物品价值为0
 */
function zeroOneBag(n, v, w, c){
  let dp = new Array(v+1).fill(0)

  for(let i=1; i<n+1; i++){
    // 注意：第二层循环要逆序循环，逆序循环保证每个物品只能用一次
    // 如果顺序循环的话，当j>c[i]，去取dp[j-c[i]]的时候可能已经用到了该物品，就会导致该物品被重复使用，不符合01背包要求，所以逆序循环
    for(let j=v; j>0; j--){
      if(j >= c[i]){
        // 每次都比较当前容积下是不拿当前物品的价值更高还是拿了当前物品的价值更高
        dp[j] = Math.max(dp[j], dp[j-c[i]]+w[i])
      }
    }
  }
  
}

完全背包问题

01背包问题题目要求

• 有N件物品和一个容量为V的背包
• 第i件物品的体积是Vi，其价值是Wi
• 每件物品可以无限次使用
• 要求物品体积不超过背包容量且价值最大

01背包与完全背包的区别是，完全背包中每个物品都是可以无限次使用的。

其解法与01背包的一维数组方式也是基本一致的，只需要注意容积是正序循环的，因为可以重复使用物品

/**
 * @description 0-1背包问题
 * @param {number} n 物品数量
 * @param {number} v 背包的容积
 * @param {number[]} w 物品价值数组,索引为0的物品价值为0
 * @param {number[]} c 物品体积数组,索引为0的物品价值为0
 */
function zeroOneBag(n, v, w, c){
  let dp = new Array(v+1).fill(0)

  for(let i=1; i<n+1; i++){
    // 与01背包的一维数组解法相似，只是这里可以重复使用物品所以正序循环
    for(let j=1; j<v+1; j++){
      if(j >= c[i]){
        // 对于一个物品，要么不拿为dp[j]，要么拿了为dp[j-c[i]]+w[i]
        // #而dp[j-c[i]]代表之前的状态，正序循环所以包含拿过物品i的状态
        dp[j] = Math.max(dp[j], dp[j-c[i]]+w[i])
      }
    }
  }
}

总结

0-1背包二维数组解法：

核心计算公式是dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])

参与计算的是dp[i-1]所以每个物品是只用过一次的

0-1背包一维数组解法：

核心计算公式是dp[j] = max(dp[j],dp[j-c[i]]+w[i])

因为是逆序进行的，背包容量从大往小算，刚开始的时候小容积的价值还没有计算当前物品，所以不会重复使用

完全背包：

核心计算公式dp[j] = max(dp[j],dp[j-c[i]]+w[i])，与01背包一致。

区别在于正序进行的过程中是可以对同一物品多次使用的。