#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define n  30  //  30 pour la force brute, 130 pour les autres méthodes
#define ln 22  //  13 pour la programmation dynamique, 17 pour la séparation en profondeur, 22 pour la séparation avec tas
long poids[n], utilite[n], spoids[n+1], sutilite[n+1], capacite;
long max(long a,long b) { return a>b?a:b; }
void swap(long *a,long *b) { long c=*a; *a=*b, *b=c; }
typedef struct{ long p,u,ur; int sep; enum {non,oui,no,ou} pris[n]; } sol;
sol opti, S;
#define P S.p
#define U S.u
#define Ur S.ur
#define Sep S.sep
#define Pris S.pris
void aff(sol S)
{ int i;
  char c=' ';
  for(i=0;i<n;i++) if(Pris[i]&1) printf("%c(%d:%ld,%ld)",c,i,poids[i],utilite[i]), c='+';
  printf("=(%ld,%ld)\n",P,U);
}
void afff(sol S)
{ int i;
  for(i=0;i<n;i++) printf("%d",Pris[i]);
  printf(" p=%ld u=%ld ur=%ld sep=%d\n",P,U,Ur,Sep);
}
void place(int j)
{ if(P>capacite) return;  // gagne la moitié du temps de calcul
  if(U+sutilite[j]<=opti.u) return;
  if(j--)
  { U+=utilite[j], P+=poids[j], Pris[j]=1, place(j),
    U-=utilite[j], P-=poids[j], Pris[j]=0, place(j);
  } else
  if(P<=capacite && U>opti.u) opti=S;
}
void forcebrute()
{ int j;
  for(j=n;j--;) Pris[j]=0;
  P=U=0, opti=S;
  place(n);
}
void progdyn()
{ long p, (*f)[capacite+1]=calloc(n+1,sizeof(*f)); int j; 
  if(!f) { printf("mémoire insuffisante pour la programmation dynamique\n"); return; }
  for(j=0;j<n;j++)
   for(p=0;p<=capacite;p++)
    f[j+1][p]= p>=poids[j] ? max(f[j][p-poids[j]]+utilite[j],f[j][p]) : f[j][p];
  for(p=capacite,j=n;j--;)
   if((Pris[j]=f[j][p]!=f[j+1][p])) p-=poids[j];
  U=f[n][P=capacite-p], opti=S;
  free(f);
}
struct { sol *t; int s,m; } tas; //struct { sol t[tas.m]; int s,m; } tas;
#define t(i) tas.t[(i)-1]
void  pop()
{ sol b=t(tas.s--);
  int i=1, j;
  S=t(1);
  for(;j=2*i,j+=j<tas.s&&t(j).ur<t(j+1).ur,j<=tas.s&&t(j).ur>b.ur;i=j) t(i)=t(j);
  t(i)=b;
}
void range()
{ if(Ur<=opti.u||Ur<U) return;
  int j, i=tas.s+=!tas.s||t(tas.s).ur>opti.u;
  if(i>tas.m) tas.t=realloc(tas.t,(tas.m*=2)*sizeof(S))?:(free(tas.t),NULL);
  if(!tas.t) {printf("Le tas déborde\n"), tas.m=tas.s=0; return; }
  for(;(j=i/2)&&Ur>t(j).ur;i=j) t(i)=t(j);
  t(i)=S;
}
#undef t
void eval()
{ int j;
  P=U=Ur=0; Sep=n;
  for(j=n;j--;) if(Pris[j]==oui) U+=utilite[j], P+=poids[j];
  if(P>capacite) return;
  for(j=0;j<n;j++) if(Pris[j]>1)
  Pris[j]= P+poids[j]<=capacite ? P+=poids[j],U+=utilite[j],ou : (Ur=Ur?:U+(capacite-P)*utilite[j]/poids[Sep=j],no);
  Ur=Ur?:U;
  if(U>opti.u) opti=S;
}
void sepeval()
{ int j,e;
  for(j=n;j--;) Pris[j]=2;
  tas.s=0, tas.t=calloc(tas.m=1000,sizeof(S));
  eval(), opti=S, range();
  while(tas.s&&(pop(),Ur>opti.u)) for(j=Sep,e=2;e--;) Pris[j]=e, eval(), range();
  free(tas.t);
}
void separe()
{ if(Ur<=opti.u||Ur<U) return;
  int sep=Sep, j;
  sol s[2];
  for(j=2;j--;) Pris[sep]=j, eval(), s[j]=S;
  int k=s[1].ur<s[0].ur;
  for(j=2;j--;) S=s[j^k], separe();
}
void sepevalprof()
{ int j;
  for(j=n;j--;) Pris[j]=2;
  opti.u=-1;
  eval();
  separe();
}
void afftemps()
{ static long unsigned t=0; long unsigned u=clock(), d=u-t;
  if(d) printf(" %ld.%06ld\n",d/1000000lu,d%1000000lu);
  t=u;
}
int main()
{ long unsigned i, j, m=(1<<ln)-1;
  for(capacite=n*m/2,i=j=n;i--;) j=j*5+1, utilite[i]=(poids[i]=(j&m)+m/2)^(j>>ln)%8u, Pris[i]=1;
  for(j=n;j--;) for(i=j;i--;) if(poids[i]*utilite[j]>poids[j]*utilite[i]) swap(poids+i,poids+j), swap(utilite+i,utilite+j);
  for(*spoids=*sutilite=i=0;i<n;i++) spoids[i+1]=spoids[i]+poids[i], sutilite[i+1]=sutilite[i]+utilite[i];
  eval(), aff(S), afftemps();
  if(ln<=22        ) printf("séparation et évaluation avec tas\n"),      sepeval    (), aff(opti), afftemps();
  if(ln<=17        ) printf("séparation et évaluation en profondeur\n"), sepevalprof(), aff(opti), afftemps();
  if(capacite*n<1e8) printf("programmation dynamique\n"),                progdyn    (), aff(opti), afftemps();
  if(n<=30         ) printf("force brute\n"),                            forcebrute (), aff(opti), afftemps();
  return 0;
}