动态规划_背包问题_初始化与遍历顺序的讨论

• 参考: 代码随想录

最近在跟着 代码随想录 刷了两遍背包问题, 初步掌握了 01背包 与 完全背包 问题模型, 并且已编写相关理论总结; 然而我对于动态规划的初始了解中仅重点关注了: 状态定义, 状态转移方程, 边界问题; 近期做题发现, 初始化与遍历顺序亦对问题有着关键性的形象; 这里对初始化与遍历顺序进行简单的讨论;

引子: 背包问题该如何定义

背包问题,可以分为纯背包问题与背包衍生问题; 不同的问题定义,自然会存在不同的问题模型;

对于纯背包问题 就是可以转换符合 01背包, 完全背包, 多重背包等, 其问题定义往往是这样的:

• 01背包: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品仅能够装一次, 问这个背包可以装的最大价值是多少?
• 完全背包: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品数量无限制, 问这个背包可以装的最大价值是多少?
• 多重背包: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品数量有自己的限制, 问这个背包可以装的最大价值是多少?

对于背包衍生问题, 其本质上也是背包问题, 只是问题的定义略有不同, 比如:

• 01背包衍生: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品仅能够装一次, 问这个背包恰好装满的最大价值?
• 01背包衍生: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品仅能够装一次, 问这个背包恰好装满的组合数?
• 完全背包衍生: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品数量无限制, 问这个背包恰好装满的最大价值?
• 完全背包衍生: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品数量无限制, 问这个背包恰好装满的组合数?
• 完全背包衍生: 有N件物品,和一个容量(衡量单位为重量)为W 的背包, 物品i 的重量为 weight[i], 价值为 value[i]. 每件物品数量无限制, 问这个背包恰好装满的排列数?
• … 还可以很多很多

对于背包衍生问题在实际的题目中是更常出现的事情, 归根到底其考察的是对于动态规划中五个关键点的理解到不到位:分别是状态定义, 状态转移方程, 边界定义, 初始化, 遍历顺序; 而对于状态定义, 状态转移方程, 边界定义 这三点不在本篇的讨论范围; 而初始化与遍历顺序会因问题不同, 有所限制; 瞎猫碰到死耗子是经常的事儿, 这导致动态规划算法中我个人一致不重视其逻辑理解, 这也是本篇的初衷;

初始化

初始化问题指的是除了边界位置外的 dp 数组的初始化问题;

初始化问题就我当前刷过的题目而言, 并没有一个实际的标准; 其往往需要需要根据状态定义, 状态转移方程 而定, 而状态的定义又与题目中问题的定义息息相关; 这里举两个例子感受一下:

• 目标排列数 : 定义为dp[j] 和为 j 的排列数; 状态转移为: dp[j] += dp[j-numsp[i]]; 初始化 0 就是合适的;
• 最少零钱和: 定义为 dp[j] 表示组成j 面额的组合中数量最少的值; 状态转移为: dp[j] = min(dp[j], dp[j-coin] + 1); 初始化为最大值是合适的 (1 << 32) - 1;

无需特定去查看当前题目描述,

• 关于状态定义对初始化的影响:
  • 如果是恰好背满的情况, 那么应当初始化为-∞, 比较合适. 这说明在初始时, dp[1] 是不合法的状态,应当为-∞;
  • 如果是尽可能的装满, 那么应当初始化为0, 因为dp[1]初始时还没有价值, 也是合法的;
• 关于状态转移对初始化的影响:
  • 如果状态转移方程中包括 min, max 等标识符, 那么应保证min, max 时可以有效取值. 比如min 情况, 取0 是不合适的,因为0已经时小值了,这隐藏了真实的逻辑结果; max 同理; 这并没有定论, 只是需要符合题意;

遍历顺序

对于背包问题遍历顺序可以分为两个点进行讨论: 1.正序逆序问题; 2.先物品,先背包问题;

正序逆序问题:

正序与逆序本身没有问题, 问题在于其与状态转移方程是嘻嘻相关的; 一般的状态转移方程是与左上方的状态有关, 我以此为例讨论, 例如01背包 的状态转移方程为 dp[j] = max(dp[j], dp[j-weight[i]] + value[i]), 其仅与上方与左前方的状态有关;

• 如果采用正序遍历: 那就是无限取值, 适用于完全背包问题;

  这是因为在遍历过程中, 状态转移方程仅考虑到当前位置能否取值, 没有记录当前物品是否已经取过值了;而前方的数组是已经经历过取值问题了, 所以是无限取值问题;这也就是一维滚动数组的问题;

• 如果采用逆序遍历: 那就是仅取值一次, 适用于01背包问题;

  这在遍历过程中,从后向前遍历, 对于当前位置而言,前方数组还没有判定过, 当前获得物品就是第一次获得;这就是背包问题;

先背包先物品问题

对于背包问题,存在两种遍历顺序: 先遍历物品, 再遍历背包; 或者 先遍历背包再遍历物品;

他们的差别点在于:

• 先遍历物品再遍历背包: 这是一种组合问题, 如果题目中要求获得组合数, 那么必须如此遍历;

  至于为何是组合问题呢? 因为优先遍历物品, 也就是说最终结果一定是 {物品1, 物品2, 物品3}的结果;

• 先遍历背包再遍历物品: 这是一种排列问题;, 如果题目中要求获得排列数, 那么必须如此遍历;

  至于为何是排列问题呢? 因为优先遍历背包, 也就是说最终结果是 {物品1, 物品2, 物品3}, {物品3, 物品2, 物品1}等的结果;对于每一个背包位置均经历了物品1, 物品2, 物品3 的多次洗礼;

对于01背包仅能够优先遍历物品;
对于纯完全背包问题如何遍历是一样的;
对于组合型完全背包: 仅能够优先遍历物品;
对于排列型完全背包: 仅能够优先遍历背包;