背包模板大全|环球信息

01背包：有n个物品，每个物品的重量分别为: w[1],w[2],...,w[n];

【资料图】

每个物品的价值分别为：v[1],v[2],...,v[n];

现有一个载重为T的背包，问如何装才能使得背包中物品总价值最高；

(每个物品只有唯一一个)

代码模板：

for(int i=1;i<=n;i++)

for(int j=T;j>=w[i];j--)

f[j]=max(f[j],f[j-w[i]]+v[i]);

f[j]表示面对前i个物品时，载重为j的背包能装的最大价值；

f[T];

完全背包：有n种物品，每种物品的重量分别为: w[1],w[2],...,w[n];

每种物品的价值分别为：v[1],v[2],...,v[n];

现有一个载重为T的背包，问如何装才能使得背包中物品总价值最高；

(每个物品可以不限量装)

代码模板：

for(int i=1;i<=n;i++)

for(int j=w[i];j<=T;j++)

f[j]=max(f[j],f[j-w[i]]+v[i]);

f[j]表示面对前i个物品时，载重为j的背包能装的最大价值；

多重背包：有n种物品，每种物品的重量分别为: w[1],w[2],...,w[n];

每种物品的价值分别为：v[1],v[2],...,v[n];

每种物品提供的数量为：p[1],p[2],...,p[n];

现有一个载重为T的背包，问如何装才能使得背包中物品总价值最高；

(每个物品均有一定数量，不可无限量装)

代码模板：

for(int i=1;i<=n;i++)

for(int j=T;j>=w[i];j--)

for(int k=0;k<=min(j/w[i],p[i]);k++)

f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);

f[j]表示面对前i个物品时，载重为j的背包能装的最大价值；

二维费用模板：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cmath>

#include<math.h>

#include<stdlib.h>

#include<string.h>

#include<float.h>

using namespace std;

int n,p,q,w[1010],v[1010],c[1010],f[1010][1010];

int main()

{

freopen("nasa.in","r",stdin);

freopen("nasa.out","w",stdout);

cin>>q>>p>>n;

for(int i=1;i<=n;i++)

scanf("%d %d %d",&w[i]/*体积*/,&v[i]/*重量*/,&c[i]/*卡路里*/);

for(int i=1;i<=n;i++)

for(int j=p;j>=w[i];j--)

for(int k=q;k>=v[i];k--)

f[j][k]=max(f[j][k],f[j-w[i]][k-v[i]]+c[i]);

cout<<f[p][q];

return 0;

}

标签：