背包问题模板

01背包

特点：每件物品最多只能用一次

01背包问题

题意

给出每件物品的体积v,价值w,求解能装入背包的的物品的最大价值，并且每件物品只能选一次

思路

那么这道题就是典型的01背包问题，对于每件物品都存在两种状态，选还是不选。

就像以下图展现的那样，同时我们还要注意，在选择第i件物品时，要判断背包能否放得下。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10000];
int f[10000][10000];
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;for(int j=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v)f[i][j]=max(f[i][j],f[i][j-v]+w);}} cout<<f[n][m]<<endl;
}

优化

现在我们对他进行优化，使用一维数组

1.将二维数组转换为一维数组

我们发现，在用二维数组进行计算时，我们的f[i] [j] 与f[i-1] [j] 时相互独立的，但换成一维数组后，f[j]并不能很好的区分f[i] [j] 与f[i-1] [j]，所以我们使用逆序。

2.只有在j>=v时，才会选择第i件物品，那我们逆序结束标志就变成了j>=v。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10000];
int f[10000];
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;for(int j=m;j>=v;j--){//这里的f[i][j]=f[i-1][j]也去掉是因为用一维数组表示f[j]=f[j],没多大意义f[j]=max(f[j],f[j-v]+w);}} cout<<f[m]<<endl;
}

完全背包

特点：每件物品有无限个

题意

给出每件物品的体积v,价值w,求解能装入背包的的物品的最大价值，并且每件物品能选无限次。

思路

对于每件物品的状态，我们可以不选，也可以选k件

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10000];
int f[10000][10000];
void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;for(int j=0;j<=m;j++)for(int k=0;k*v<=j;k++)f[i][j]=max(f[i][j],f[i-1][j-v*k]+w*k); }cout<<f[n][m]<<endl;
}
signed main()
{int t=1;
//	cin>>t; while(t--)solve();	
}

优化

代码优化

1.这样替换过后，就不必要开第三层循环。

2.我们再回顾01背包 f[i] [j] =max( f[i] [j], f[i-1] [j-v]+w)

那同样的我们可以将他准换一维数组，但有所不同的就是，我们不用再担心会将i-1个物品覆盖。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10000];
int f[10000];
void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int v,w;cin>>v>>w;for(int j=v;j<=m;j++)f[j]=max(f[j],f[j-v]+w); }cout<<f[m]<<endl;
}
signed main()
{int t=1;
//	cin>>t; while(t--)solve();	
}

多重背包

特点：每件物品可以用有限个

题意

给出每件物品的体积v,价值w,求解能装入背包的的物品的最大价值，并且每件物品的个数是有限的

思路

那我们就发现了，我们的多重背包与完全背包的朴素计算方法是类似的,唯一要注意的就是，我们第三层循环的k要小于等于物品个数。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[10000];
int f[10000][10000];
void solve()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;for(int j=0;j<=m;j++)for(int k=0;k*v<=j&&k<=s;k++)f[i][j]=max(f[i][j],f[i-1][j-v*k]+w*k); }cout<<f[n][m]<<endl;
}
signed main()
{int t=1;
//	cin>>t; while(t--)solve();	
}

优化

那么这里就存在疑问了，为什么不能像完全背包一样优化？

将其展开我们发现，并不能通过知道五个数的最大值，推出来前4个数的最大值。所以这种优化方式是错的。

这里我们有一个小技巧，使用二进制去优化。

用二进制去打包这些物品，比如说我有10个物品，我按照二进制，将其打包成

1，2，4，以及最后剩下的3。这样我们去询问时，就是第一堆（1个）物品取还是不取，第二堆（2个）物品取还是不取…。也就是将他转换成了01背包的问题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[100000],w[100000];
int f[100000];
void solve()
{int n,m;cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++)//在此处理分组问题，{int a,b,s;cin>>a>>b>>s;int k=1;//标记二进制的大小while(k<=s){cnt++;//用来记录第几组v[cnt]=a*k;//每组的体重w[cnt]=b*k;//每组的价值s-=k;k*=2;//更新剩余数量，以及每组分配的大小} if(s>0)//判断是否还有剩余的没有分配{cnt++;v[cnt]=a*s;w[cnt]=b*s;} } n=cnt;//更新//用01背包解决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;}
signed main()
{int t=1;
//	cin>>t; while(t--)solve();	
}

分组背包

特点：每组最多可以选一个物品

题意

给出每件物品的体积与价值。每组有若干个物品，最多只能选一个，求解能装入背包的的物品的最大价值。

思路

代码

这里优化和上边类似，就不再描述了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[10000];
int v[11000][10000];
int w[10000][10000];
int s[100000];
signed main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>s[i];for(int j=0;j<s[i];j++){cin>>v[i][j]>>w[i][j];}} for(int i=1;i<=n;i++){for(int j=m;j>=0;j--)for(int k=0;k<s[i];k++)if(v[i][k]<=j)f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}cout<<f[m]<<endl;
}