黄鑫的博客

动态规划

4/26/2024 DP

# 参考资料

动态规划的精髓就是**选或不选**

经典题目是 0-1背包 和 完全背包

  • 0-1背包 是每个物品只能被选择一次
  • 完全背包 则是每个物品随意选择任意次数

# 0-1 背包

有 n 个物品，第 i 个的体积为 w[i]，价值为 v[i]，每个物品最多选一次，求体积和不超过 capacity 的最大价值和。

当第 i 个物品被选择时，剩余体积就减去 w[i]，否则剩余体积不变。

动态规划需要最麻烦的就是定义 dfs 二维数组（一般是二维），不过 dfs 总是得到我们要的东西，即 最大价值和，而 dfs 的两个参数就是这道题一直在变的量：

  • 物品 i
  • 剩余体积 c

价值已经在dfs中返回了

那么我们定义 dfs(i, c) 函数：返回选择前 i 个物品，在剩余体积为 c 时，能达到的最大价值和。

那么对于物品 i：

  • 选，剩余体积需要减去 w[i]，但在比较时可以得到 v[i] 的价值优势
  • 不选，体积和价值都不变
dfs(i, c) = Math.max(dfs(i-1,c), dfs(i-1,c-w[i]) + )

边界条件：

  • i 变成负数了，已经选完了物品，此时只能返回 0，因为没有物品就没有价值
  • 剩余的体积小于 当前选择物品的体积，那么就只能不选，直接返回 dfs(i-1, c) ，因为体积是不变的
function zero_one_package(capacity, w, v){

  function dfs(i, c){
    if(i<0){
      return 0
    }
    if(w[i] > c){
      return dfs(i-1, c)
    }
    return Math.max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i])
  }
  return dfs(w.length - 1, capacity)
}

# 记忆化搜索

这里的 dfs 可以加上记忆化搜索，就是对于特定参数的dfs 函数，在求到值后通过数组 cache 记下来。

  • 有两个参数就是二维数组，参数的最大可能值 + 1 就是数组的长度（因为从 0 开始）
  • 定义一个不可能达到的初始值（比如最大价值不可能是 -1），return 之前如果 cache 里面不是这个初始值，就直接返回cache里面的值
  • 在每个dfs返回的时候，顺便把值填入 cache 里面就行了
function zero_one_package(capacity, w, v){
  const cache = new Array(w.length).fill(0).map(()=>new Array(capacity + 1).fill(-1)) // change

  function dfs(i, c){
    if(i<0){
      return 0
    }
    if(w[i] > c){
      return dfs(i-1, c)
    }
    if(cache[i][c] !== -1){ // change
      return cache[i][c]
    }
    return cache[i][c] = Math.max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i]) // change
  }
  return dfs(w.length - 1, capacity)
}

# 变形

  • 体积不超过 capacity 时，求装物品的 方案数/最大价值和

  • 体积恰好等于 capacity 时，求装物品的 方案数/最大价值和

  • 体积最少为 capacity 时，求装物品的 方案数/最小价值和

  • 当求方案数的时候，就不需要考虑价值了，所以这个 v 数组完全可以不给。

  • 同时 Math.max 也变成了加法，因为当前物品选择或者不选是两种方案，变成了

    • 从前 i-1 种物品中，在剩余容量为 c 时的方案数（不选i）
    • 加上 从前 i-1 种物品中，在剩余容量为 c - w[i] 时的方案数（选择i）

  • 最开始的 return 0 也需要改，因为之前我们需要的价值和是在 return 的时候通过 v[i] 加起来的，现在要改成，根据体积判断，

    • 如果是体积不超过 capacity， 那么剩余体积 c 就要 大于0
    • 如果是体积恰好等于 capacity，那么剩余体积 c 就要 等于0

下面是 体积恰好等于 capacity 时，求装物品的 方案数

function zero_one_package(capacity, w, v){
  const cache = new Array(w.length).fill(0).map(()=>new Array(capacity + 1).fill(-1))

  function dfs(i, c){
    if(i<0){
      return c === 0 ? 1 : 0
    }
    if(w[i] > c){ // 恰好等于还是不能超，所以这个判断还存在
      return dfs(i-1, c)
    }
    if(cache[i][c] !== -1){
      return cache[i][c]
    }
    return cache[i][c] = dfs(i-1, c) + dfs(i-1, c-w[i])
  }
  return dfs(w.length - 1, capacity)
}