#include<stdio.h>
#define n 20             // nombre d'objets
int v[n]={2,5,3,4,7,6},  // volume des objets
    u[n]={3,7,4,5,6,5},  // utilité des objets
    c=16;                // capacité du sac
/* c=256*n/4   c=(v[0]+v[1]+...)/2
20->1687             1701
30->2633             2578
80->8130             7784
150->14805          14807
300->30070  2s      29804  37s
400->40093          39971  4m10s   */
int v[n],u[n],c;

typedef struct { enum {inte,obli,lais,pris} t[n]; int min,maj,sep;} noeud;
noeud opti;
void eval(noeud *a)
{ int su=0, sv=0, j;
  for(j=n;j--;) if(a->t[j]==obli) su+=u[j], sv+=v[j];  // somme des utilités et des volumes des objets obligatoires
  a->min=su, a->maj=-1;
  if(sv>c) return;                 // Le sac déborde déjà avec seulement les objets obligatoires.
  for(j=0;j<n;j++) if(a->t[j]>1)   // Les objets facultatifs pris dans l'ordre (u/v décroissant)
  { if(sv+v[j]<=c) su+=u[j], sv+=v[j], a->t[j]=pris; else     // sont mis dans le sac s'il y reste assez de place.
    if(a->t[j]=lais, a->maj<0) a->sep=j, a->maj=su+(c-sv)*u[j]/v[j]; // Le premier objet qui déborde est pris en partie.
  }
  a->min=su;
  if(a->maj<0) a->maj=su;   // Tous les objets facultatifs tiennent dans le sac.
  if(su>opti.min) opti=*a;  // On a trouvé une solution réalisable encore meilleure.
}
void separe(noeud a)
{ if(a.maj<=opti.min) return;  // Le noeud ne contient pas de solution meilleure qu'opti (ou est vide si a.maj<0)
  noeud b=a;
  a.t[a.sep]=inte, eval(&a);   // L'objet sep est interdit dans a
  b.t[b.sep]=obli, eval(&b);   // et obligatoire dans b
  if(a.maj>b.maj) separe(a), separe(b);  // On étudie d'abord l'option la plus prometteuse
  else            separe(b), separe(a);
}
void aff(noeud a)
{ int j;
  for(j=0;j<n;j++) if(a.t[j]&1) printf("%d,%d,%d ",j,u[j],v[j]);
  printf(" %d<=%d\n",a.min,a.maj);
}
int main()
{ int j, k, x;
  if(n!=6)
  { for(c=k=0,j=n;j--;) u[j]=k=(5*k+1)%256, c+=v[j]=k=(5*k+1)%256;
    c=1?c/2:256*n/4;
  }
  if(0) for(k=n;--k;) if(729*729%(k/(k&-k))==0) for(j=0;j+k<n;j++) if(u[j]*v[j+k]<u[j+k]*v[j]) x=u[j],u[j]=u[j+k],u[j+k]=x,x=v[j],v[j]=v[j+k],v[j+k]=x; //tri shell
  if(1) for(k=n;k--;)                           for(j=0;j  <k;j++) if(u[j]*v[j+1]<u[j+1]*v[j]) x=u[j],u[j]=u[j+1],u[j+1]=x,x=v[j],v[j]=v[j+1],v[j+1]=x; //tri à bulle

  for(j=n;--j;) if(u[j]*v[j-1]>u[j-1]*v[j]) return printf("Les objets ne sont pas ordonnés par u/v décroissant\n"), 1;
  for(j=n;j--;) opti.t[j]=lais;  // Tous les objets sont facultatifs
  eval(&opti);     // On doit toujours appeler eval() avant separe()
  separe(opti);    // recherche de la solution optimale
  aff(opti);       // affichage de la solution optimale
  return 0;
}