背包问题 — 对于体积的限制不同对应的模板变动规律总结

对于各种各样的背包问题，对体积的限制都略有不同，对应的我们的代码也会有一点小区别，通过观察发现基本上大部分的题，都是对应某个类型的背包问题然后套用模板，对于同一类型的问题，如果体积限制不同，代码也是极其类似的，唯一的不同就是初始化的方式不同，这也直接导致了最终结果的变化，为自己做一点学习总结，方便回顾，这里不对背包类型做分析，参考每个类型的模模板即可，这里只对体积的范围做一个规律总结，只需在使用模板的基础上根据体积的范围对初始化做一些变动即可。

注：只用于自己复习总结，编写较为简陋，参考了xdd大佬的分享，具体可以看原文https://www.acwing.com/blog/content/458/

分析

结果状态方程：f[n][m] 当前状态方程：f[i][j] 第i个物品的体积：v

• 前 n 个物品体积最多是 m 的选法求最大值

  • 从实际出发，体积最多是 m ，所以当 0 <= j <= m 时，方案合法，默认初始化即可，另外循环时要保证 j - v >= 0，因为如果最多是 -x(负数) ，那么任何一种情况都不满足最多是 -x(负数) 的情况，所以 j - v <= 0 的情况不合法，不能转移过来

• 前 n 个物品体积恰好是 m 的选法求最大值/最小值

  • 从实际出法，体积恰好是 m ，所以当 j == m 时，方案合法，但是 j < m 或 j > m 都是不合法的方案，而要想所有方案都是合法转换过来的，需要保证状态只能从 f[0][0] 转移过来，所以求最大值/最小值时，需要在最开始将除了 f[0][0] 的所有状态都初始化为 -INF / INF ，另外循环时要保证 j - v >= 0，因为体积恰好是 -x(负数)的情况不合法，不能转移过来

• 前 n 个物品体积至少是 m 的选法求最小值

  • 从实际出发，体积至少是 m ，所以当 j <= v <= m 时，方案合法，但当 i == 0 时，f[0][j](j>0) 一定是不合法的，只有 f[0][0] 时最小值才为0，所以状态也只能从 f[0][0] 转移过来，所以要将除了 f[0][0] 的所有状态都初始化为 INF ，另外，因为当体积至少是 -x(负数)的情况是合法的，任何一个自然数都至少是 -x(负数)，所以 j - v 可以为负数，所以循环时可以遍历 0~j ，但是当 j - v <= 0 时需要特判一下将其改为0，因为数组下标没有负数，并且至少为负数也等同于至少为0

• 前 n 个物品体积最多是 m 的选法求方案数

  • 要求体积最多是 m ，所以体积小于等于 m 都合法，所以 j $\in$ [0 , j] 都合法，所以 f[0][0~j] 的方案数都为1，都需要初始化为1

• 前 n 个物品体积恰好是 m 的选法求方案数

  • 要求体积恰好是 m，那么只要体积不为 m 就不合法，所以 i == 0 时只有 f[0][0]==1，所以只需要将 f[0][0] 初始化为1即可

• 前 n 个物品体积至少是 m 的选法求方案数

  • 要求体积至少是 m，要求体积不能低于 m，所以当 i == 0 时，j > 0 的所有情况都是不合法的，因为0个物品体积只能为0，所以只有 f[0][0] 的方案数为1，只需要初始化 f[0][0] = 1 即可

结论

求最大值/最小值初始化总结

• 朴素版

  • 体积至多 j，f[i][j] = 0，循环 v <= j <= m
  • 体积恰好 j，
    • 当求价值的最小值：f[0][0] = 0, 剩下的是INF，循环 v <= j <= m
    • 当求价值的最大值：f[0][0] = 0, 剩下的是-INF，循环 v <= j <= m
  • 体积至少 j，f[0][0] = 0，剩下的是INF，循环 0 <= j <= m

• 维度压缩

  • 体积至多 j，f[i] = 0，循环 v <= j <= m
  • 体积恰好 j，
    • 当求价值的最小值：f[0] = 0, 剩下的是INF，循环 v <= j <= m
    • 当求价值的最大值：f[0] = 0, 剩下的是-INF，循环 v <= j <= m
  • 体积至少 j，f[0] = 0，剩下的是INF，循环 0 <= j <= m

求方案数初始化总结

• 朴素版

  • 体积至多 j，f[0][i] = 1，循环 v <= j <= m
  • 体积恰好 j，f[0][0] = 1，循环 v <= j <= m
  • 体积至少 j，f[0][0] = 1，循环 0 <= j <= m

• 维度压缩

  • 体积至多 j，f[i] = 1，循环 v <= j <= m
  • 体积恰好 j，f[0] = 1，循环 v <= j <= m
  • 体积至少 j，f[0] = 1，循环 0 <= j <= m