title: 背包问题 - 01背包 、完全背包 、多重背包、还有混合背包
tag: [算法, C++, 背包]
date: 2021/04/08
主要讲三个背包：背包，完全背包，多重背包。
主要讲四个背包：
背包，完全背包，多重背包，混合背包。
01 背包
01背包的意思是选一个或者不选。
朴素版：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1111;
int v[N]; //v[i]表示i个物品的价值
int w[N]; //w[i]表示第i个物品的重量
int f[N][N]; //f[i][j]表示在容量为j的情况下，选i个物品的最大值
int n, m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n ;i++)cin >> v[i] >> w[i];
//数据输入
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++){
f[i][j] = f[i - 1][j]; //如果不选的话，前面的状态要推到后面去。
if(j>=v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
//f[i][j]的最大值，是前一个状态推出来，选第i个物品或者不选
//不选的话，f[i][j] = f[i - 1][j]
//选的话，f[i][j] = f[i-1][j - w[i]] + v[i]，前一个状态(i-1) + 第i件物品
//容量至少需要w[i],加上以后会减少w[i]的容量,所以需要减去这部分的重量，再加上v[i]的价值。
cout << f[n][m]<<endl;
return 0;
}优化：
这里我们可以发现，其实每次最多只用到了f [ i ]的前一个状态f[ i -1 ],那么其实有些是不需要的额，我们可以用滚动数组解决。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1111;
int v[N], w[N], f[N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n ;i++)cin >> v[i] >> w[i];
//数据输入
for(int i = 1;i <= n;i++)
for(int j = m;j >= v[i];j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m]<<endl;
return 0;
}完全背包：
完全背包是一个物品可以选很多个，没有上限
朴素版：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1111;
int v[N], w[N], f[N][N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n ;i++)cin >> v[i] >> w[i];
//数据输入
for(int i = 1;i <= n;i++)
for(int j = 0;j <= m;j++)
for(int k = 0;k * v[i] <= j;k++)//一个物品选k个，开始枚举，到装不下为止
f[i][j] = max(f[i][j], f[i-1][j - v[i] * k] + w[i] * k);
cout<<f[n][m]<<endl;
return 0;
}朴素版的代码很容易超时，也是因为这个，我不敢保证这里的代码是否正确。因为我之前验证代码的时候就报了Time Limit Exceeded。
优化一下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N][N],n,m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n; i++)cin >> v[i] >> w[i];
for(int i = 1;i <= n; i++)
for(int j = 0;j <= m; j++)
{
f[i][j] = f[i - 1][j];
if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}优化x2:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N];
int f[N],n,m;
int main(){
cin >> n >> m;
for(int i = 1;i <= n; i++)cin >> v[i] >> w[i];
for(int i = 1;i <= n; i++)
for(int j = v[i];j <= m; j++)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout<<f[m]<<endl;
return 0;
}多重背包：
多重背包就是每个物品有 s[i] 个的上限限制的完全背包。
所以朴素的写法：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 111;
int v[N],w[N],s[N],n,m,f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k<=s[i] && k * v[i] <= j ;k++)
f[i][j] = max(f[i][j],f[i-1][j - k*v[i]] + k*w[i]);
cout<<f[n][m]<<endl;
return 0;
}这种写法也容易报超时，这个代码在数据量小的时候可以过。
优化一下：
思路是把s[i]件物品拆成k个，用一个2进制数来表示。
比如1023件。就拆成1 ，2 ，4，8，16， 32， 64， 128， 256， 512。或者说，我们在枚举的时候不是一个一个枚举。而是跳着跳着枚举
通过这种方式，我们可以表示出0～1023的所有数，也就是把1023拆成了10个小物品。每个物品做一个01 背包。
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 25000; //M = 2000 * log2000
int n,m,cnt;
int V[M],W[M],f[M];
int a,b,s;
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a >> b >> s;
int k = 1;
while(k <= s){
cnt++; //物品是1序，所以先cnt++
V[cnt] = k * a;
W[cnt] = k * b;
s -= k;
k *= 2;
//按照之前的设想拆开来
}
if(s > 0){
//如果还有剩的，直接当成一个物品打包加上去就行
cnt++;
V[cnt] = s * a;
W[cnt] = s * b;
}
}
//开始 01 背包
for(int i = 1;i <= cnt;i++)
for(int j = m;j >= V[i];j--)
f[j] = max(f[j], f[j -V[i]] + W[i]);
cout << f[m] << endl;
return 0;
}
混合背包
混合背包是说，物品有 只能选一次的，无数次的，s次的
就是上面三种背包混合在一起了
思路是这样：
如果只有两类物品：一类物品只能取一次，另一类物品可以取无限次，那么只需在对每个物品应用转移方程时，根据物品的类别选用顺序或逆序的循环即可，复杂度是O(VN)。
伪代码
for i=1..N
if 第i件物品属于01背包
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
else if 第i件物品属于完全背包
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]};再加上多重背包
如果再加上有的物品最多可以取有限次，那么原则上也可以给出O(VN)的解法：遇到多重背包类型的物品用单调队列解即可。但如果不考虑超过NOIP范围的算法的话，用P03中将每个这类物品分成O(log n[i])个01背包的物品的方法也已经很优了。
当然，更清晰的写法是调用我们前面给出的三个相关过程。
for i = 1...N
if 第i件物品属于01背包
ZeroOnePack(c[i],w[i])
else if 第i件物品属于完全背包
CompletePack(c[i],w[i])
else if 第i件物品属于多重背包
MultiplePack(c[i],w[i],n[i])混合背包思路参考的这篇博客