#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], 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(j--)
  { Pris[j]=0, place(j), U+=utilite[j], P+=poids[j],
    Pris[j]=1, place(j), U-=utilite[j], P-=poids[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 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(U=P=0,j=n;j--;) U+=utilite[j], P+=poids[j];
  aff(S), afftemps();
  if(n<=30         ) printf("force brute\n"),                            forcebrute (), aff(opti), afftemps();
  return 0;
}