lin511238427 2011-11-21 01:27:00
点我顶贴
收藏
删除
#include<stdio.h>
int n,v;
int a[2005],b[2005],c[2005];
int f[2005][505];
int min(int a,int b)
{
if(a<b)
return a;
else return b;
}
int main()
{
int i,j,k,l;
scanf("%d%d",&n,&v);
for(i=1;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(i=1;i<=n;i++)
for(j=1;j<=v;j++)
{
if(j>=b[i]){
l=min(a[i],j/b[i]);
for(k=0;k<=l;k++)
{
if(f[i-1][j-k*b[i]]+k*c[i]>f[i][j])
f[i][j]=f[i-1][j-k*b[i]]+k*c[i];
}
}
else f[i][j]=f[i-1][j];
}
printf("%d\n",f[n][v]);
getch();
return 0;
}
在RQ混了一年了才100AC,着实有愧啊,不过菜鸟也会有明天,哈哈……