动态规划之背包问题
背包问题 （Knapsack problem）是一种组合优化 的NP完全 问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
也可以将背包问题描述为决定性问题，即在总重量不超过$W$的前提下，总价值是否能达到$V$。
定义
我们有$n$种物品，物品$i$的重量为$w_i$，价值为$v_i$
我们假定所有物品的重量和价值都是非负数，背包所能承受的最大重量为$W$。
$$
\begin{align}
最大化 & \quad \sum^{n}_{i=1}{v_{i} x_i} \\
受限于 & \quad \sum^{n}_{i=1}{w_{i} x_i} \leq W, \quad x_i \in \{0,1\} \\
\end{align}
$$
如果限定物品$i$最多只能选择$b_i$个，则问题称为多重背包问题（有界背包问题） 。
可以用公式表示为：
如果不限定每种物品的数量，则问题称为完全背包问题（无界背包问题） 。
各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。
01背包
设一共有$N$件物品，第$i$件物品的重量为$w[i]$，价值为$v[i]$，最大总重量为$W$。
如果采取暴力枚举方法，每件物品都存在装入和不装入两种情况，所以时间复杂度为$O(2^n)$，使用动态规划可以把时间复杂度控制在$O(N*W)$。求解的总目标是背包物品的总价值，变量有是否放入物品 和书包限重 。
定义$dp[i][j]$表示将前$i$件物品放入限重为$j$的书包可以获得的最大价值，其中$0 \leq i \leq N, \ 0 \leq j \leq \ W$。
状态转移：
不装入第$i$物品：$dp[i][j] = dp[i-1][j]$
在能装入的前提下，装入第$i$件物品：$dp[i][j]=dp[i-1][j-w[i]]+v[i]$
即状态转移方程为：
1 dp[i][j] = max (dp[i-1 ][j], j-w[i] >= 0 ? dp[i-1 ][j-w[i]]+v[i] : 0 )
由状态方程可知，dp[i][j]的值只与dp[i-1][0,…,j-1]有关，所以可以采用滚动数组对空间优化。需要注意的是，为了防止上一层循环dp[0,…,j-1]被覆盖，需要逆向枚举 $j$（空间优化前没有这个限制）。代码如下：
1 2 3 4 5 6 7 8 9 10 int solution01Knapsack (int N, int W, std::vector<int > &w, std::vector<int > &v) std::vector<int > dp (W+1 ) ; for (auto i = 0 ; i < N; i++) { for (auto j = W; j >= w[i]; j--) { dp[j] = std::max (dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; }
时间复杂度为$O(NW)$，空间复杂度为$O(W)$。第$i$件物品装入或者不装入而获得的最大价值完全可以由前面$i-1$件物品的最大价值决定，暴力枚举忽略了这个事实。
完全背包
设一共有$N$件物品，第$i$件物品的重量为$w[i]$，价值为$v[i]$，每件可以无限多个，最大总重量为$W$。
与01背包非常相似，状态dp定义一致，只是状态转移稍微不同：
不装入第$i$物品：$dp[i][j] = dp[i-1][j]$（同01背包）
在能装入的前提下，因为每件物品有无限个，所以不从$dp[i-1][j-w[i]]$转移，而是从$dp[i][j-w[i]]$转移，即装入第$i$种商品后还可以再继续装入该种商品。即装入第$i$件物品：$dp[i][j]=dp[i][j-w[i]]+v[i]$
状态转移方程为：
1 dp[i][j] = max (dp[i-1 ][j], j-w[i] >= 0 ? dp[i][j-w[i]]+v[i] : 0 )
和01背包问题相似，也可以进行空间优化，不同点在于完全背包的$j$只能正向枚举 而01背包只能逆向枚举，因为$max$第二项是dp[i]而01背包是dp[i-1]，即完全背包需要覆盖而01背包需要避免覆盖。代码如下：
1 2 3 4 5 6 7 8 9 10 int solutionUnboundedKnapsack (int N, int W, std::vector<int > &w, std::vector<int > &v) std::vector<int > dp (W+1 ) ; for (auto i = 0 ; i < N; i++) { for (auto j = w[i]; j <= W; j++) { dp[j] = std::max (dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; }
完全背包问题也可以转化为01背包问题来解：将一种物品转换成最多能放下的若干件。
最简单的想法是，考虑到第$i$种物品最多装入$W/w[i]$件，于是把第$i$种物品转化为 $W/w[i]$件费用及价值不变的物品，然后求解这个01背包问题。时间复杂度为：$O(NW\frac{\sum{\frac{W}{w_i}}}{N}) = O(W\sum{\frac{W}{w_i}})$ 。
更高效的转化方法是采用二进制的思想：把第$i$种物品拆成重量为$w_i 2^k$、价值为$v_i 2^k$若干件物品，其中 k 取遍满足$w_i 2^k \leq W$的非负整数。这是因为不管最优策略选几件第$i$种物品，总可以表示成若干个刚才这些物品的和（例：$13 = 2^0 + 2^2 + 2^3$）。这样就将转换后的物品数目降成了对数级别。时间复杂度为：$O(NW\frac{\sum\log_2{\frac{W}{w_i}}}{N}) = O(W\sum\log_2{\frac{W}{w_i}})$。
多重背包
设一共有$N$件物品，第$i$件物品的重量为$w[i]$，价值为$v[i]$，数量限制为$n[i]$，最大总重量为$W$。
参考完全背包转为01背包的思想，$k$表示装入第$i$种物品的件数，k <= min(n[i],j/w[i])
1 dp[i][j] = max{(dp[i-1][j-k*w[i]]+k*v[i]) for range(k)}
同理也可以进行空间优化，而且$j$也必须逆向枚举 ：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 int solutionBoundedKnapsack (int N, int W, std::vector<int > &w, std::vector<int > &v, std::vector<int > &n) std::vector<int > dp (W + 1 ) ; for (auto i = 0 ; i < N; i++) { for (auto j = W; j >= w[i]; j--) { for (auto k = 1 ; k <= std::min (n[i], j / w[i]); k++) { dp[j] = std::max (dp[j], dp[j - k * w[i]] + k * v[i]); } } } return dp[W]; }
时间复杂度为：$O(NW\bar n) = O(W\sum{n_i})$，空间复杂度为：$O(W)$。
当然也可以采用二进制思路，将第$i$种物品分成了$log_2{n_i}$件物品，将时间复杂度优化为：$O(W\sum{\log_2{n_i}})$。
杂项
背包问题还有一些其他变种问题。
恰好装满
要求：必须恰好装满背包。
只需要修改初始化，将$dp[0,…,N][0]$初始为0，其它$dp$值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。
总方案数
要求：求背包装满或则装至某一指定容量的总方案数。
修改转移方程中的$max$为$sum$。
二维背包
上文讨论的背包都只有一个限制：最大容量。二维背包指一个背包存在两个限制（比如重量和体积限制）。
此类问题的解法和一维背包相似，需要$dp$数组要多开一维，其他和一维背包一致。
输出最优方案
要求：输出背包问题的解方案。
可以参照一般动态规划的方案输出方法：记录每一个状态是由那条策略推导而出，以便回溯出上一个状态。
以01背包为例，再开辟一个数组$P[i][j]$来记录方案，$P[i][j]=0$表示$dp[i][j]$采用第一种状态转移策略，即$dp[i][j] = dp[i-1][j]$，$P[i][j]=1$表示采用第二种状态转移策略，即$dp[i][j]=dp[i-1][j-w[i]]+v[i]$，从而反推方案。
另外我们也可以从求出的$dp$数组进行反推，若 $dp[i][j] = dp[i−1][j]$ 说明未选第$i$个物品，反之说明选了。
.png)