背包问题是典型的动态规划问题。
问题描述
背包问题是一种组合优化的NPC（NP完全）问题，可以描述为：
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，如何选择是的物品的总价格最高。
采用动态规划算法，是求解背包问题的一般思路，具体可分为以下几类：
１、01背包问题
２、完全背包问题
3、多重背包问题
01背包问题
问题描述
一共有N件物品，第i（i > 0）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包上限W的情况下，求能装入背包的最大价值。
问题分析
定义状态dp: $dp[i][j]$表示将前i件物品装进限重为j的背包可以获得的最大价值。
则 \(dp[i][j] = max(dp[i−1][j], dp[i−1][j−w[i]]+v[i]), j \ge w[i]\)
得到伪代码
dp[0,...,W] = 0
for i = 1,...,N
for j = W,...,W[i]
dp[j] = max(dp[j], dp[j-w[i]]+v[i])
算法时间复杂度O(NW)，空间复杂度O(W)。
完全背包问题
问题描述
完全背包问题相比于01背包问题，每种物品可以有无限个。
问题分析
状态dp与01背包问题中定义一致，区别在于装入第i种物品，此时不应转移到$dp[i-1][j-w[i]]$而是$dp[i][j-w[i]]$，即装入第i种商品后还可以继续装入该种商品。
则 \(dp[i][j] = max(dp[i−1][j], dp[i][j−w[i]]+v[i]), j \ge w[i]\)
得到伪代码
dp[0,...,W] = 0
for i = 1,...,N
for j = w[i],...,W
dp[j] = max(dp[j], dp[j-w[i]]+v[i])
算法时间复杂度O(NW)，空间复杂度O(W)。
完全背包问题与01背包问题解法不同在于前者只能正向枚举而后者只能逆向枚举。
多重背包问题
问题描述
多重背包问题相对于上述两种背包问题，不同在于每种物品是有限个。
问题分析
状态
\[dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for every k}\]其中，k为装入第i种物品的件数, $k \le min(n[i], j/w[i])$
得到伪代码
dp[0,...,W] = 0
for i = 1,...,N
for j = W,...,W[i]
for k = [0, 1,..., min(n[i], j/w[i])]
dp[j] = max(dp[j], dp[j-k*w[i]]+k*v[i])
算法时间复杂度$O(NWn) = O(W\sum{_i}{n_i})$
其他情形
恰好装满
只有容量为0的背包可以在什么都不装的情况下恰好装满，其他容量的背包初始均没有合法解。
因此，将dp[0,…N]初始为0，其他dp值初始化为-inf。
求方案总数
将状态转移中max改为sum
\[dp[i][j] = sum(dp[i−1][j], dp[i][j−w[i]]), j \ge w[i]\]二维背包
每个背包有两个限制（如重量和体积限制），此时需要dp维度+1。