Bin Packing难题是一个优化问题，其中不同尺寸的物品必须包装到有限数量的箱子或容器中，每个箱子都有固定的给定容量，以最小化使用的箱子数量。
当箱的数量限制为1并且每个项目都以体积和值为特征时，最大化可以放入箱子的项目的价值的问题称为 背包问题。
变体#
-
不同体积的物品应该按顺序到达，决策者必须决定是选择并包装当前观察到的物品，还是不处理, 每个决定都不能撤销。
-
相应的，离线包装就是已知所有物品，那么做决策的时候就可以重新排列物品。
-
背包问题就是一个特定的离线包装问题，其中每个物品都有一个体积和价值，同时包的数量限制为1。
背包问题算法#
给定一组项目，每个项目都有一个权重和一个值，确定要包含在集合中的每个项目的数量，以便总重量小于或等于给定的限制，并且总值尽可能大。
0-1 背包问题#
限制每类项目的副本数为1或者0
定义子问题 P(i, W) 为：在前 i 个物品中挑选总重量不超过 W 的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作 m(i, W) ，其中 1 <= i <= n， 1 <= W <= C。
考虑第 i 个物品，只有两种选择：
- 选：背包容量减小，问题变为
P(i-1, W-W[i]) - 不选：背包容量不变，问题变为
P(i-1, W)
同时考虑临界情况，只有一个物品的情况下，最大价值就是该物品的价值，当然也可能该物品直接超过了背包的最大容量。但这是确定的，因此我们是可以按照这个规则反向推导出 m(i, W) 的。
分析到这里，它已经满足动态规划的条件：
- 问题可以分解为有限子问题
- 能够归纳出状态转移方程：
m(i, W) = max{m(i-1, W), m(i-1, W-W[i]) + V[i]} - 临界条件：
i = 0, m(i, W) = 0;W = 0. m(i, W) = 0
总结下：
| 0, i = 0
| 0, W = 0
m(i, W) =|
| m(i-1, W), W[i] > W
| max{m(i-1, W), m(i-1, W-W[i]) + V[i]}, otherwire无界背包问题#
限制每类项目的副本数为最大为非负整数C。
有界背包问题#
每类项目的副本数量没有限制。