Memory Limit: 32768 KB
DD and his girlfriend love travelling, one day they go to a strange cave. DD suddenly found some valuable stones and water named "wistone" and "owenwater". If DD could take them to the outer world, he could earn a lot:) Unfortunately, DD only takes a bottle
with capacity W with him. He can only use this bottle to take them back.
As you know, each type of "wistone" and "owenwater" has different value, and "wistone" cannot be divided into smaller ones while "owenwater" can be taken as much as you want if it is avaliable.
Now, you are asked to calculate the maximum value DD can take back.
Input
This problem contains several test cases, you should process it to the end of input.
For each test case, there are two integers in the first line, N (1 <=
N <= 100) and W ( 0 <= W <= 50000), N indicates the total type number of "wistone" and "owenwater".
W indicates the capacity of bottle.
Then next n lines, each line contains three integers, ai, bi (1 <= ai, bi
<= 1000) and ti. ai indicates the amount, bi indicates the total value and if ti
is 0, it means this one is "wistone" otherwise it is "owenwater".
Output
For each test case, you should only output one number(accurate to 2 digits to the right of the decimal point), namely the maximum value DD can get.
Sample Input
3 150 100 100 0 100 100 0 130 10 1
Sample Output
103.85
省赛之前,来道背包练练手。
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,w,i,j; double maxx[500007]; struct note { int a,b; double value; }water[107],stone[107]; int cmp(const note a,const note b) { return a.value>b.value; } int main() { while(scanf("%d%d",&n,&w)!=EOF) { int a,b,c,count_w=0,count_s=0; while(n--) { scanf("%d%d%d",&a,&b,&c); if(!c) { stone[count_s].a=a; stone[count_s++].b=b; } else { water[count_w].a=a; water[count_w].b=b; water[count_w++].value=(double)b/(double)a; } } memset(maxx,0,sizeof(maxx)); for(i=0;i<count_s;i++)//01背包 for(j=w;j>=stone[i].a;j--) { if(maxx[j]<maxx[j-stone[i].a]+stone[i].b) maxx[j]=maxx[j-stone[i].a]+stone[i].b; } sort(water,water+count_w,cmp); int tv=0,tw=0; double ans=maxx[w]; for(i=0;i<count_w;i++)//完全背包 { for(j=0;j<=water[i].a;j++) { if(w-j-tw<0)break; if(ans<maxx[w-j-tw]+j*water[i].value+tv) ans=maxx[w-j-tw]+j*water[i].value+tv; } tv+=water[i].b; tw+=water[i].a; } printf("%.2f\n",ans); } return 0; }