背包模板大全|环球信息
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;
}
