本文主要是介绍背包问题中的“至少至多恰好”问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
前言
对于背包问题的至少，至多，恰好问题，他们的状态转移方程其实是不变的，需要考虑的只有初始化的问题和一些特殊点的特判
这里的二维指的是没有状态优化的二维，而不是二维费用\
求方案数初始化
二维情况
1、体积至多j，f[0][i] = 1, 0 <= i <= m，其余是0
2、体积恰好j，f[0][0] = 1, 其余是0
3、体积至少j，f[0][0] = 1，其余是0 状态转移max(0,..)
从状态定义的本身出发
一维情况
1、体积至多j，f[i] = 1, 0 <= i <= m，
2、体积恰好j，f[0] = 1, 其余是0
3、体积至少j，f[0] = 1，其余是0 状态转移max(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（只会求价值的最小值）
这篇关于背包问题中的“至少至多恰好”问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
