01背包:有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int f[N][N],v,w;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
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-1][j-v]+w);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
完全背包问题:有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
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=v[i];j<=m;j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
多重背包问题:有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n,m;
int f[N][N],v[N],w[N],s[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=0;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-v[i]*k]+w[i]*k);
}
}
}
cout<<f[n][m]<<endl;
}
多重背包问题(数据范围特别大大,二进制优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N=25000,M=2010;
int f[M],v[N],w[N];
int n,m;
int main()
{
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 ;
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;
}
分组背包问题:
有 N 组物品和一个容量是 V 的背包。
每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int s[N];
int v[N][N],w[N][N];
int n,m;
int f[N];
int main()
{
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;
}
混合背包问题:
有 N 种物品和一个容量是 V 的背包。
物品一共有三类:
第一类物品只能用1次(01背包);
第二类物品可以用无限次(完全背包);
第三类物品最多只能用 si 次(多重背包);
每种体积是 vi,价值是 wi。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int f[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
int v,w,s;
cin>>v>>w>>s;
if(s==0)
{
for (int j = v; j <= m; j ++ )
f[j] = max(f[j], f[j - v] + w);
}
else
{
if(s==-1) s=1;
for (int k = 1; k <= s; k *= 2)
{
for (int j = m; j >= k * v; j -- )
f[j] = max(f[j], f[j - k * v] + k * w);
s -= k;
}
if(s>0)
{
for (int j = m; j >= s * v; j -- )
f[j] = max(f[j], f[j - s * v] + s * w);
}
}
}
cout<<f[m]<<endl;
}