四种背包问题模版
相似度极高,很好背。
01背包
原题链接
#include<bits/stdc++.h>
using namespace std;
int f[1010];
int n,v;
int main()
{
cin>>n>>v;
for(int i = 1;i <= n;i ++)
{
int v1,w1;
cin>>v1>>w1;
for(int j = v;j >= 1;j --)
if(v1 <= j)
f[j] = max(f[j],f[j-v1] + w1);
}
cout<<f[v];
return 0;
}
完全背包
原题链接
#include<bits/stdc++.h>
using namespace std;
const int N = 1100;
int f[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1;i <= n;i ++)
{
int v1,w1;
cin>>v1>>w1;
for(int j = 0;j <= m;j ++)
if(v1<=j)
f[j] = max(f[j],f[j-v1]+w1);
}
cout<<f[m];
return 0;
}
多重背包
原题链接
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[1000];
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i ++)
{
int v1,w1,s1;
cin>>v1>>w1>>s1;
for(int j = m;j >= 0;j --)
{
for(int t = 0;t <= s1;t ++)
{
if(t*v1<=j)
f[j] = max(f[j],f[j-t*v1]+t*w1);
}
}
}
cout<<f[m];
return 0;
}
分组背包
原题链接
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[1000],s[1000],v[1000][1000],w[1000][1000];
int main()
{
cin>>n>>m;
for(int i = 1;i <= n;i ++)
{
cin>>s[i];
for(int j = 1;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 t = 1;t <= s[i];t ++)
{
if(v[i][t]<=j)
f[j] = max(f[j],f[j-v[i][t]]+w[i][t]);
}
}
}
cout<<f[m];
return 0;
}