01背包问题
__蒟蒻__
·
·
个人记录
背包问题可分三种，01背包、完全背包以及多重背包。
什么是01背包？
在“01背包问题”中,f_{ij}记录“将前i件物品放入容量为j的背包中”的最大价值，考虑当前第i件物品的策略（放或不放），如果不放的i件物品，那么问题就转化为“前i-1件物品放入容量为j的背包中”，最大价值为f_{i-1,j}；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为j-v_i的背包中”，此时能获得的最大价值就是f_{i-1,j-v_i}再加上放入第i件物品获得的价值p_i。
我们来看一道题：
P1060 开心的金明
1.状态的设计：
|花费$/$元|0|1|2|3|4|5|6|7|8|9|10|边界|
|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|:----------:|
|阶段0|0|0|0|0|0|0|0|0|0|0|0||
|阶段1|0|0|0|0|0|0|0|0|1600|1600|1600|取价格$800$的物品|
|阶段2|0|0|0|0|2000|2000|2000|2000|2000|2000|2000|取价格$400$的物品|
|阶段3|0|0|0|1500|2000|2000|2000|3500|3500|3500|3500|取价格$300$的物品|
|阶段4|0|0|0|1500|2000|2000|2000|3500|3500|3500|3500|取价格$400$的物品|
|阶段5|0|0|400|1500|2000|2000|2400|3500|3500|3900|3900|取价格$200$的物品|
**2.状态转移方程：**
$f_{i,j}=max(f_{i-1,j-v_i}+v_i \times w_i,f_{i-1,j})$（$1\le i\le m,v_i\le j\le n$）
$f_{i,0}=0$（$1\le i\le m$），$f_{0,j}=0$（$0\le j\le n$）
该算法的时间复杂度为$\Theta(nm)$，参考程序如下：
```cpp
#include<iostream>
using namespace std;
int n,m,v[27],w[27],f[27][30002];
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(j>=v[i])f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+v[i]*w[i]);
else f[i][j]=f[i-1][j];
cout<<f[m][n]<<endl;
return 0;
}
```
**3.优化空间：**
以上方法的空间复杂度为$\Theta(nm)$，可以优化到$\Theta(n)$。
首先，我们知道$f_{i,j}$是由$f_{i-1,j}$和$f_{i-1,j-v_i}$两个子问题决策而来；也就是说第$i$阶段只与第$i-1$阶段有关，可以使用滚动数组来优化空间。
继续分析，若将$f_{i,j}$改为一维数组$g_j$，并将上面程序中$for(int$ $j=1;j<=n;j++)$循环改为：
$for(int$ $j=n;j>=v[i];j--)$，这样顺序计算$g_i$时，可以保证$g_{j-v_i}$保存的是前一阶段的状态$f_{i-1,j-v_i}$的值。
改进的程序如下：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,v[27],w[27],f[30002];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>v[i]>>w[i];
for(int i=1;i<=m;i++)
for(int j=n;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]);
cout<<f[n];
return 0;
}
```
**其他$01$背包的题目：**
[P1048 采药](https://www.luogu.com.cn/problem/P1048)
**小结：**
$01$背包是最基本的背包问题，它包含了背包问题中划分阶段、确定状态、建立状态转移方程的基本思想，其他类型的背包问题往往也可以转化成$01$背包问题求解