#include<stdio.h>
#include<stdlib.h>
#if 0
#define n 5
const int poids  []={6,8,9,7,5},
          utilite[]={7,9,8,6,4},
          capacite=20;
#else
#define n 8
const int poids  []={ 2, 1, 3, 6, 3, 2, 2, 4},
          utilite[]={12, 6,10,18, 8, 5, 4, 3},
          capacite=10;
#endif
typedef struct{ int min,maj,sep; enum{pris,rejete,pri,rej} etat[n]; } noeud;
noeud h;
void evalue(noeud *a)
{ int i, po=a->min=a->maj=0;
  for(i=0;i<n;i++)        // Chacun des objets   
   if(a->etat[i]==pris)   //  qui est imposé   
   { po+=poids[i];        //  est ajouté dans le sac. On compte son poids
     a->min+=utilite[i];  //   et son utilité.
   }
  if(po>capacite) return; //  Si le sac déborde déjà avec les objets imposés, il n'y a pas de solution réalisable (min>0=maj)
  for(i=0;i<n;i++)        //  Chacun des objets (dans l'ordre des utilité/poids décroissants)
   if(a->etat[i]>rejete)  //    qui n'a pas encore été pris ou rejeté définitivement
   { if(po+poids[i]<=capacite)  // est mis dans le sac s'il reste assez de place pour lui.
     { po+=poids[i];            //  On compte son poids  
       a->min+=utilite[i];      //   et son utilité.
       a->etat[i]=pri;          //   On note qu'il a été mis dans le sac.
       continue;                //   Puis on passe à l'objet suivant.
     }
     a->etat[i]=rej;            // S'il ne tient pas dans le sac, on note qu'on ne le prend pas.
     if(a->maj) continue;       // Si le majorant n'a pas encore été calculé
     a->maj=a->min+(capacite-po)*utilite[i]/poids[i]; // alors on le calcule en comptant l'utilité d'une partie de l'objet.
     a->sep=i;                  // On fera la séparation en imposant ou en rejetant cet objet pris en partie.
   }
  if(a->maj<a->min) a->maj=a->min; // Si tous les objets tiennent dans le sac, l''évaluation est exacte.
  if(h. min<a->min) h=*a;          // Si on trouve une meilleure solution réalisable, on la garde.
}
void separe(noeud *a)
{ if(a->maj<a->min) return;  // noeud vide
  if(a->maj<=h.min) return;  // Ce noeud ne contient pas de meilleure solution réalisable que la meilleure déjà trouvée.
  { noeud b=*a, c=*a;
    b.etat[b.sep]=pris;    evalue(&b);
    c.etat[c.sep]=rejete;  evalue(&c);
    if(b.maj>c.maj) separe(&b), separe(&c); // On commence par le fils le plus prometteur.
    else            separe(&c), separe(&b);
  }
}
void affn(noeud *a)
{ if(a->maj<a->min) printf("pas de solution\n");
  else
  { int i, u=0, p=0;
    for(i=0;i<n;i++)
     if(a->etat[i]%2==pris) printf(" %d:%d/%d ",i,utilite[i],poids[i]), u+=utilite[i], p+=poids[i];
    printf("  utilite=%d   poids=%d\n",u,p);
  }
}
int main()
{ int i;
  for(i=1;i<n;i++) if(utilite[i]*poids[i-1]>utilite[i-1]*poids[i]) printf("%d/%d<%d/%d\n",utilite[i-1],poids[i-1],utilite[i],poids[i]), exit(1);
  for(i=0;i<n;i++) h.etat[i]=pri;
  evalue(&h);
  separe(&h);
  affn(&h);
  return 0;
}