【总结】背包问题的至多/恰好/至少

原贴

一、学习过程总结

一开始学背包问题时遇到的大多数的状态表示是：从前\(i\)个物品中选，且总体积至多是\(j\)的问题。

慢慢地在提高课中，就有出现状态表示是：从前\(i\)个物品中选，且总体积恰好是\(j\)的问题。例如 ，求的是恰好是\(j\)的总方案数问题。

同时还出现了状态表示是：从前\(i\)个物品中选，且总体积至少是\(j\)的问题。例如 ，求的是总体积至少是\(j\)的最小价值。

可以观察到，他们的分析方法以及状态转移方程都是一样的，唯独是初始化有很大的不同。

二、求方案数初始化总结

二维情况

1. 体积至多\(j\), \(f[0][i] = 1\), \(0 <= i <= m\)，其余是\(0\)
2. 体积恰好\(j\), \(f[0][0] = 1\), 其余是\(0\)
3. 体积至少\(j\), \(f[0][0] = 1\), 其余是\(0\)

一维情况

1. 体积至多\(j\), \(f[i] =1\), \(0 <= i <= m\)
2. 体积恰好\(j\), \(f[0] =1\), 其余是\(0\)
3. 体积至少\(j\), \(f[0] =1\), 其余是\(0\)

三、求最大值最小值初始化总结

二维情况

1. 体积至多\(j\)，\(f[i,k] = 0\)，\(0 <= i <= n, 0 <= k <= m\)（只会求价值的最大值）
2. 体积恰好\(j\):

• 当求价值的最小值：\(f[0][0] = 0\), 其余是\(INF\)
• 当求价值的最大值：\(f[0][0] = 0\), 其余是\(-INF\)

3. 体积至少\(j\)，\(f[0][0] = 0\)，其余是\(INF\)（只会求价值的最小值）

一维情况

1. 体积至多\(j\)，\(f[i] = 0, 0 <= i <= m\)（只会求价值的最大值）
2. 体积恰好\(j\):

• 当求价值的最小值：\(f[0] = 0\), 其余是\(INF\)
• 当求价值的最大值：\(f[0] = 0\), 其余是\(-INF\)

3. 体积至少\(j\)，\(f[0] = 0\)，其余是\(INF\)（只会求价值的最小值）