动态规划学习—01 背包问题

01 背包问题背景

  • 拥有固定容量大小的背包
  • 有 n 种物品, 每种物品只能取 1 次
  • 需要返回背包能装下的最大价值

暴力解法

  • [dfs(深度优先搜索算法) / 回溯]

    列出所有情况, 最后返回最大价值

动态规划解法

基础解法: 二维数组

动规五部曲:

    1. 确定dp[i][j]数组下标含义
    • i 表示编号为**[0 - i]**的物品均判断过
    • j 表示容量为 j 的背包
    • dp[i][j]表示容量为 j 的背包, 在[0 - i]物品中能装下的最大价值
    1. 递推公式

    根据dp[i][j]的定义可以知道:

    判断容量为 j 的背包最大值(即dp[i][j])时

    只需要判断本次加入的物品**( i 物品)**是否需要放入背包

    那么只有两种情况 :

    • 放入 i 物品

    由于需要放入 i 物品, 那么当前背包的价值, 应该是 :

    ​ 判断完了[0 到 i - 1]物品价值的容量 j 的背包容量减去 i 物品的重量, 价值加上 i 物品的价值

    故背包价值为 : dp[i - 1][j - weight[i]] + value[i]

    • 不放入 i 物品

      不放入 i 物品, 那么此时背包的价值容量应该都不变, 也就是和判断完了[0 到 i - 1]物品的背包最大价值相同

​ 故背包价值为 : dp[i - 1] - 1[j]

​ 要取得最大价值, 则此时背包的价值应该取两种情况的最大者

​ 想到这里, 递推公式也就出来了 :

1
2
3
4
5
6
/*
 * 放入物品   dp[i - 1][j - weight[j]] + value[i]
 * 不放入物品 dp[i - 1][j]
 * 原因可以参考上面的讲解
 */
dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i - 1][j]);
    1. dp 数组的初始化

    • 将容量为 0 的背包初始化为 0

    • 第一种物品对应的容量满足的所有背包初始化成第一种物品的价值

    • 其余部分的初始化无意义, 因为不会用到这些部分, 初始化任何数都可以

    1. 确定遍历顺序

    由于使用的是二维数组, 定义了两个变量 i 和 j 背包和物品的依赖关系被解耦了,所以遍历顺序并不会影响结果的正确性

    • 先遍历背包, 再遍历物品

      _由数组下标要大于零可知, 当 j - weight[i]小于 0 时, 只能选择不放入物品 i , 因为背包的容量不够 _

    • 先遍历物品, 再遍历背包

    1. 举例推导 dp 数组
    • 假设背包容量为 3
    所需容量 价值
    物品 0 1 15
    物品 1 2 20
    物品 2 3 30
    👇 为 i, 👉 为 j 0 1 2 3
    0 0 15 15 15
    1 0 15 20 35
    2 0 15 20 35

    斜体表示 : 初始化设置的值, 粗体表示 dp 数组遍历得到的值

​

进阶解法 : 一维数组

滚动数组理论基础

​ 观察基础解法的递推公式, 发现新一层都需要使用上一层的值结果, 那么我们是否可以从后往前更新, 由于后面的数据需要用到上一层的结果, 此时, 上一层的结果还未更新, 保留在对应位置, 按照逆序更新, 就可以将二维数组压缩成一维数组

​ 这种逆序更新的思想,就类似于一个滚筒(类似滚动转场)或者和翻页的感觉类似, 称为滚动数组的思想

    1. dp 数组的含义

      dp[j],将数组下标变量定义为 j, 目的是为了和一维数组保持一致便于理解

      • ​ j 表示容量为 j 的背包
      • dp[j] 表示容量为 j 的背包所能装载的最大价值

    1. 递推公式

      同二维数组的思想相同, 根据滚动数组的定义则有 :

      dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) //i 表示遍历物品时的编号

      ​

    1. dp 数组初始化

      和二维数组的想法类似, 应该将容量为 0 的和小于物品[0]重量的背包初始化为 0

      (实际上应该初始化的值应该比最小的 value 还要小) : 防止 dp 数组的值被覆盖

    1. 遍历顺序

      由于使用了滚动数组, 所以遍历顺序需要注意:

      • 遍历顺序应该先遍历物品, 再遍历背包

        递推的逻辑是,每次只判断当前该物品是否应该加入到 j 容量的背包

        如果先遍历背包再遍历物品, 则需要则得到的正确数据会被重复刷新, 恢复成为遍历状态

        (描述的不是很清楚, 但是建议通过对二维数组的模拟来体会)

      • 遍历背包时, 应该采用倒序

        因为滚动数组需要借用当前行当作上一行的数据, 所以需要从后往前更新, 上一行的数据才不会被提前覆盖

    1. dp 数组的推导模拟

      略