背包问题简介
背包问题解释
背包问题是动态规划中的经典问题，本节中会讲到多种背包问题，并对各种背包问题进行优化与转化。背包问题是指在一个有容积或者重量限制的容器中放入物品，每一个物品有不同的重量、容积、价值，要求在容器的承受范围内取得的价值最大。根据物品的限制条件不同，背包问题可以分为$01$背包、完全背包、多重背包、分组背包和混合背包问题。
背包问题的探索
在过去，有无数人尝试通过不同的贪心手段解决这一系列问题，最终都会被一种反例推翻，所以对于背包问题，贪心是无解的，必须使用动态规划。
背包问题的求解方案
$01$背包
$01$背包是在$n$件物品取出若干件放在空间为$W$的背包里，每件物品的体积为$w_1$，$w_2$至$w_n$，与之相对应的价值为$v_1$，$v_2$至$v_n$。$01$背包可谓是背包问题中最简单的问题。$01$背包的约束条件是给定几种物品，每种物品有且只有一个，并且有权值和体积两个属性。在$01$背包问题中，因为每种物品只有一个，对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中，则不需要处理。如果选择将其放入背包中，由于不清楚之前放入的物品占据了多大的空间，需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
无优化
给定n种物品，每种物品都有重量$w[i]$和价值$v[i]$，每种物品只有一个，另外，背包的容量为$W$，求在不超过背包容量的情况下将哪些物品放入背包，才可以使背包中的物品价值之和最大，假设每种物品只有一个，要么放入（$1$）。要么不放入（$0$），所以叫做$01$背包。
假设第$i$阶段表示处理第$i$件物品，第$i-1$阶段表示处理第$i-1$件物品，则当处理第$i$件物品时，第$i-1$件物品已经被处理掉，只需要考虑第$i-1$阶段下个第$i$阶段的转移。
那么我们设定状态，$dp[i][j]$表示将前i件物品放入容量为j的背包中获得的最大价值。
那么第i种物品的处理状态包括以下两种：
- 不放入：放入背包中的价值不增加，那么问题就转化成了前$i-1$件物品放入容量为j的背包中获得的最大价值，最大价值为$dp[i-1][j]$。
- 放入：在第$i$种物品放入之前为第$i-1$阶段，相当于从第$i-1$阶段向第$i$阶段转化。问题转化为将前$i-1$种物品放入容量为$j-w[i]$的背包中获得的最大价值，此时获得的最大价值就是$dp[i-1][j-w[i]]$，再加上放入放入第$i$种物品获得的价值$v[i]$，那么总价值就是$dp[i-1][j-w[i]]+v[i]$。
当背包的容量不足是，则肯定不能放入，所以价值仍为前i-1种物品处理后的结果，若背包容量充足，则考虑是否放入。那么我们就可以得出转移方程：
$$dp[i][j]=\begin{cases}dp[i-1][j],&j \lt w[i]\\\max\{dp[c[i-1][j],dp[i-1][j-w[i]]+v[i]\}，&j \ge w[i]\end{cases}$$
对于初始化，我们要将第$0$种物品或者是背包容量为$0$的情况下的$dp[]$值全部设置为$0$。
对于循环阶段，我们需要先枚举每一个物品，然后从小到大或者是从大到小枚举每一种背包容量。
答案即为$dp[n][w]$。
for(int i=1;i<=n;i++){
for(int j=W;j>=0;j--){
if(j>=w[i])
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
else
dp[i][j]=dp[i-1][j];
}
}
$01$背包优化$1$
我们可以看到，每一件物品的结果只与上一行有关，所以就可以进行滚动数组优化，将原来的记录物品的一维转化为$0/1$当状态为$dp[0][j]$时，它的上一物品的状态就是$dp[1][]$，反之，上一维状态是$dp[1][j]$时，它的上一物品的状态就是$dp[0][]$。这样我们将第二维空间大小压缩了下来。
$01$背包优化$2$
还有一种更优的滚动数组的方法，当我们从大到小枚举背包空间的时候，我们调用的都是当前背包容量或小于当前背包容量的状态，而大于当前背包容量的状态不会再用到，所以我们从大到小枚举当前背包容量的时候，可以直接覆盖掉去过的值，因为这个值已经用不到了。
但是要记住，一定要从大到小枚举，如果从小到大，那么原本还要使用的值就被覆盖掉了，原先不带第i个物品的值就会变成带第i个物品的值，会出现一件物品取多次的情况。
转移方程：
$$dp[j]=\max\{dp[j],dp[j-w[i]]+v[i]\}$$
for(int i=1;i<=n;i++)
for(int j=W;j>=w[i];j--)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
完全背包
给定n种物品，每种物品都有重量w_i和价值v_i，其数量没有限制。背包容量为W，求解在不超过背包容量的情况下如何放置物品，使得背包中物品的价值之和最大。
假设第i阶段表示处理第i种物品，因为第i种物品可以被多次放入，所以相当于从第i阶段向第j阶段转移。还在想着在上一部分01背包优化2中讲到，如果背包空间从小到大枚举会出现一种物品拿多次的情况吗，这里正好用到了。
所以，我们设状态dp[i]表示将物品放入容量为j的背包中可以获得的最大价值。很容易我们可以得出转移方程：
$$dp[j]=\max\{dp[j],dp[j-w[i]]+v[i]\}$$
你会发现，这和01背包滚动数组的状态和转移方程是完全相同的，不同的就是枚举背包容量的顺序，所以，在动态规划中，考虑怎样去枚举也是很重要的。
for(int i=1;i<=n;i++){
for(int j=w[i];j<=W;j++)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
多重背包
给定$n$种物品，每种物品都有重量$w_i$和价值$v_i$，每种物品可以选多个，但是是有限制的。第i种物品有$c_i$个，背包容量为$W$，求解在不超过背包容量的前提下和放置物品，使得背包内的价值最大。
暴力拆分
这种问题我们可以暴力拆分成$01$背包问题，将多个物品看成是$c_i$个独立的物品，然后用$01$背包的方法解决该问题。
二进制拆分
有一种更加优秀的拆分方案，将第i种物品分成$c_i$件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。这个系数就是以$2$为底数的幂。因为任何数字都可以使用以$2$为底数的幂相加得到，为什么？
把这些以$2$为底数的幂全部用$2$进制表示：
$1 \Longrightarrow (1)_2$
$2\Longrightarrow (10)_2$
$4\Longrightarrow (100)_2$
$8\Longrightarrow (1000)_2$
$\vdots$
然后来凑数$x$。$x$用二进制来表示肯定是$1$和$0$组成的，然后看上面的数，每一个以$2$为底数的幂都在每个二进制位上有一个单独的$1$，其他都是$0$，也就是说，所有$1$和$0$的组合都能够被这些数字加出来。所以，以$2$为底数的幂相加可以凑出任何一个正整数。
进行二进制拆分后，$c_i$个物品被拆分成几种新物品，每种新物品只有一个，转化为$01$背包问题。
for(int i=1;i<=n;i++){
int k=1;
while(c[i]>=k){
v[++d]=k*old_v[i];
w[d]=k*old_w[i];
c[i]-=k;
k<<=1;
}
if(c[i]!=0){
v[++d]=c[i]*old_v[i],w[d]=c[i]*old_w[i];
}
}
for(int i=1;i<=d;i++)
for(int j=W;j>=0;j--){
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
分组背包
给定n组物品，第i组有c_i种物品，第i组的第j个物品有重量$w_{ij}$和价值$v_{ij}$，背包容量为$W$，在不超过背包容量的情况下每组最多选择一个物品，求解如何放置物品可使得背包中物品的价值最大化。
因为每组只能选择一个物品，所以可以将魅族都看作是一个整体，这就类似于$01$背包问题。处理第i组问题时，我们要保证前$i-1$组物品已经被处理完毕，只需要考虑从$i-1$阶段向第$i$阶段转移。
所以我们可以设置状态：$dp[j]$表示把一组中的一个物品放入容量为$j$的背包中可以获得的最大价值。下面就要根据这个状态来考虑应该如何转移。
- 若不放入第$i$组物品，那么背包的重量和价值都不会增加，问题就会转化为将前$i-1$组物品放入容量为$j$的背包中可以获得的最大价值。
- 如果放入第$i$组物品种的第$k$个物品，那么背包的重量和价值都会增加，问题就会变成将前$i-1$组物品放入容量为$j-w[i][k]$的背包中获得的最大价值。
同样的，如果价值不足，就不会向里面放物品。但是，我们放入物品是一组中的一个，所以我们还需要枚举一组物品中的每一个物品。
所以状态转移方程即为：
$$dp[j]=\max\{dp[j],dp[j-w[i][k]]+v[i][k]\}$$
for(int i=1;i<=n;i++){
for(int j=W;j>=0;j--){
for(int k=;k<=c[i];k++){
if(j>=w[i])
dp[j]=max(dp[j],dp[j-w[i][k]]+v[i][k]);
}
}
}
混合背包
如果在一个问题中有些物品只取一次（01背包），有些物品可以取无限次（完全背包），有些物品可以取的次数有一个上限（多重背包），则该种问题属于混合背包问题。
混合背包只需要将不同的背包问题通过一次判断，使用不同模式的背包解决问题即可。例如：
for(int i=1;i<=n;i++){
if(p[i]==1)//第i种物品属于01背包
for(int j=W;j>=0;j--){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
if(p[i]==2)//第i种物品属于完全背包
for(int j=w[i];j<=W;j++){
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
//...
}
