背包模型从形式上看属于二维DP。
0-1背包问题
问题描述： 有 N 个物品和一个容量为 V 的背包， 放入第 i 个物品耗费的空间是Ci，得到的价值是Wi。求解价值总和最大值？（或求解将哪些物品装入背包可使价值总和最大 ）
状态定义：
f[i][v]表示 i 个物品恰好放入一个容量为 v 的背包可以获得的最大价值。注意这个状态定义不是问题的状态，是个一般性的状态表示，代入N、V才是问题的状态。小v可以是任意一个可能的容量。
决策：
假设前一阶段的状态是最优状态（最优子结构），考虑第i个物品放还是不放。
状态转移：
物体从少到多、包容量从小到大转移状态。放的话，意味着前一个状态背包容量最大为v-Ci，即状态为f[i-1][v-Ci]+Wi，这是一个子问题。不放，意味着放不下，否则定能使价值提高，状态为f[i-1][v]。因此得到，
f[i][v] = max(f[i-1][v-Ci]+Wi, f[i-1][v])
假设前一阶段的状态是最优状态成立的条件是，可以得到类似上面的状态转移方程。
最后就是从已知的初始状态转移到问题状态。
时间复杂度：O(V*N)
完全背包
问题描述：有N种物品（每种物品无限件）和一个容量为V的背包。放入一个第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解价值总和最大值？（或求解将哪些物品装入背包可使价值总和最大 ）
状态定义：f[i][v]表示 i 种物品放入背包容量为v可以获得的最大价值。
决策：
在前一个阶段的状态基础上，考虑放第 i 种物品。
状态转移：
放的话，假设第 i 种放 k 个，此时前一个阶段状态为 f[i-1][v-k*Ci]；不放的话相当于k=0，k的范围是[0, v/Ci]，因此得到：f[i][v] = max{ f[i-1][v-kCi] + kWi | 0 <= k <= v/Ci}
当k的取值为0,1时，这就是0-1背包的状态转移方程
时间复杂度：O(V*N*sum{V/Ci})
多重背包
问题描述：有N种物品（每种物品Mi件）和一个容量为V的背包。放入第i种物品耗费的空间是Ci，得到的价值是Wi。求解价值总和最大值？（或求解将哪些物品装入背包可使价值总和最大 ）
状态定义： f[i][v]表示 i 种物品放入一个容量为v的背包可以获得的最大价值。
决策：
在前一个阶段的状态基础上，考虑放第 i 种物品。
状态转移：
放的话，假设第 i 种放 k 个，此时前一个阶段状态为 f[i-1][v-k*Ci]，不放的话相当于k=0，k的范围是[0, min(Mi, v/Ci)]，因此得到，
f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= min(Mi, v/Ci) }
时间复杂度：O(V*N*sum{min(Mi, V/Ci)})
