题目链接:
采用动态规划解决。
设f[n][x][y] 表示前n辆车装了x个装备1和y个装备2之后能装的最多的装备3的个数。
递推关系如下:
f[n][x][y] = max ( f[n - 1][x - a][y - b] + c); 其中f[0][x][y]=0
其中a和b的范围为第n辆车可以装的装备1和装备2的个数, c 为第n辆车装完a个装备1和b个装备2后可以装的装备3的个数。
通过递推求得f[n][x][y]后,可以遍历x和y(x,y的范围可以在上述递推的过程中得到)求得最终的结果。
由于f[n]只和f[n-1]有关,所以实际上 f 数组的第一维只需要2就可以(详见代码)
1 #include2 #include 3 using namespace std; 4 5 int min(int x ,int y) 6 { 7 return x y? x:y;13 }14 15 int fun(int x)16 {17 return x>0? x:0;18 }19 int f[2][501][501];20 int main()21 {22 int carNum,w1,s1,d1,w2,s2,d2,w3,s3,d3,c1,c2,c3,d4;23 int limit[101][2];24 25 int count=1;26 cin>>carNum;27 while(carNum)28 {29 cin>>w1>>s1>>d1>>w2>>s2>>d2>>w3>>s3>>d3>>c1>>c2>>c3>>d4;30 for(int i=1;i<=carNum;i++)31 cin>>limit[i][0]>>limit[i][1];32 33 int prev=0,now=1;34 int prev_max1=0,prev_max2=0,temp,n1,n2,n3;35 memset(f[0],0,sizeof(f[0]));36 37 for(int i=1;i<=carNum;i++)38 {39 memset(f[now],-1,sizeof(f[now]));40 n1=min(limit[i][0]/w1,limit[i][1]/s1);41 for(int a=0;a<=n1;a++)42 {43 n2=min( (limit[i][0]-a*w1)/w2, (limit[i][1]-a*s1)/s2 );44 if(a==0)temp=n2;45 for(int b=0;b<=n2;b++)46 {47 n3=min( (limit[i][0]-a*w1-b*w2)/w3, (limit[i][1]-a*s1-b*s2)/s3 );48 for(int h=0;h<=prev_max1;h++)49 for(int k=0;k<=prev_max2;k++)50 {51 if(f[prev][h][k]!=-1)52 f[now][h+a][k+b]=max( f[now][h+a][k+b], f[prev][h][k]+n3 );53 }54 55 }56 }57 prev_max1+=n1;58 prev_max2+=temp;59 60 int pp=prev;61 prev=now;62 now=pp;63 }//for(int i=1;i<=carNum;i++)64 //结束后prev指向的数组存有结果;65 int result=0;66 for(int i=0;i<=prev_max1;i++)67 for(int j=0;j<=prev_max2;j++)68 {69 if(f[prev][i][j]!=-1)70 {71 int groupNum=65535; //max72 if(c1!=0)73 groupNum=min(i/c1,groupNum);74 if(c2!=0)75 groupNum=min(j/c2,groupNum);76 if(c3!=0)77 groupNum=min(groupNum,f[prev][i][j]/c3);78 result=max(result,fun(i-groupNum*c1)*d1+fun(j-groupNum*c2)*d2+fun(f[prev][i][j]-groupNum*c3)*d3+groupNum*d4);79 // 开始没有加fun函数,没有考虑到i-groupNum等小于0;80 }81 }82 if(count>1)cout< < >carNum;86 87 }88 89 return 0;90 }
【版权声明】转载请注明出处