5429 多重背包
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
你有一个容量为M的背包，和N种物品。
每种物品都有三个属性，vi，wi，与ci，分别表示这种物品的体积、价值和件数。
你的任务是，从这些所给物品中，选出若干件，其体积之和不能超过背包容量，并且使所选物品的权值的和最大。
输入描述 Input Description
第一行两个整数N,M
接下来N行每行三个数vi,wi,ci描述第i件物品的属性
输出描述 Output Description
最大的权值和
样例输入 Sample Input
2 8
2 100 4
4 100 2
样例输出 Sample Output
400
数据范围及提示 Data Size & Hint
对于20%的数据，ci=1
对于60%的数据，N,M<=500,ci<=100
对于90%的数据，N,M<=3000
对于100%的数据,N,M<=7000，ci<=5000，保证答案不超过2147483647
改数据前二进制优化可过
改数据后过不了 要用单调队列优化;
f[i][j]表示前i个物品容量为j的最大值
f[i][j]=max(f[i-1][k]+(j-k)/w[i]*v[i])
变化以下
f[i][j]=max(f[i-1][k]-k/w[i]*v[i]+j/w[i]*v[i])
可以看出更新f[i][j]时只与k有关 单调队列维护f[i-1][k]-k/w[i]*v[i]的最大值即可
/* 二进制优化代码 60分 超时 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 using namespace std; int n,m,tot; int f[maxn]; int w[maxn],v[maxn]; int main() { int i,j,k; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); int s=1; while(s<z) { tot++; w[tot]=x*s; v[tot]=y*s; z-=s;s*=2; } tot++; w[tot]=x*z; v[tot]=y*z; } for(i=1;i<=tot;i++) { for(j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]); } printf("%d ",f[m]); return 0; }
/* 单调队列优化 AC 第一次打...... WA了好久 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 50010 using namespace std; int n,m,head,tail; int w[maxn],v[maxn],c[maxn]; int f[maxn],g[maxn]; int q[maxn],p[maxn]; int main() { scanf("%d%d",&n,&m); 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=0;j<=m;j++)g[j]=0; for(int j=0;j<w[i];j++) { head=1;tail=0;g[j]=f[j]; for(int k=j,t=0;k<=m;k+=w[i],t+=v[i]) { while(tail>=head&&f[k]-t>=q[tail]) tail--; tail++; q[tail]=f[k]-t; p[tail]=k; if((k-p[head])/w[i]>c[i]) head++; g[k]=q[head]+t; } } for(int j=0;j<=m;j++)f[j]=g[j]; } printf("%d ",f[m]); return 0; }