Cod sursa(job #708873)

Utilizator ScateWayScateWay ScateWay Data 7 martie 2012 13:40:22
Problema Problema rucsacului Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<stdio.h>
int x,j,t,n,i,b[3][105],k,a[105][2],max1;
int main()
{freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
scanf("%d%d",&n,&t);
for(i=0;i<n;i++) {scanf("%d",&a[i][0]);
				  b[2][i]=-1;
				 }
for(i=0;i<n;i++) scanf("%d",&a[i][1]);
b[0][0]=a[0][0];
b[1][0]=a[0][1];
for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(((a[j][0]+b[0][i])<=t && (a[j][0]+b[0][i])>max1) || ((b[1][i]+a[j][1])>=b[1][j] && (a[j][0]+b[0][i])==max1))
                                                                               {b[0][j]=b[0][i]+a[j][0];
				                                                                b[1][j]=b[1][i]+a[j][1];
				                                                                b[2][j]=i;
																				if(b[0][j]>max1) max1=b[0][j];
                                                                               }
max1=0;
for(i=0;i<n;i++) if((b[0][i]>max1 && b[0][i]<=t) || (b[1][i]>b[1][k] && b[0][i]==max1)) {k=i;
																						 max1=b[0][i];
																						}
i=k;
printf("%d\n",b[1][i]);
while(i!=-1) {printf("%d ",i+1);
	      i=b[2][i];
         }
return 0;
}