#include<stdio.h>
#include<stdlib.h>
#define n 5              // nombre d'objets
const int poids  []={7,4,5,8,6},  
          utilite[]={9,5,5,6,4},
          capacite=15,   // poids total maximal quand on maximise l'utilité
          besoin=10;     // utilité totale minimale quand on minimise le poids
typedef struct {int optrelax, realisable, objetpartiel;
                enum {obligatoire, interdit, pris, nonpris} etat[n];} noeud;
void evaluemaxutil(noeud *a)
{ int i, po=a->realisable=0;
  a->objetpartiel=-1;
  for(i=0;i<n;i++)         
   if(a->etat[i]==obligatoire)
    po+=poids[i], a->realisable+=utilite[i];
  if(po>capacite) { a->optrelax=a->realisable-1; return; }
  for(i=0;i<n;i++) if(a->etat[i]>interdit)
  { if(po+poids[i]<=capacite)
     po+=poids[i], a->realisable+=utilite[i], a->etat[i]=pris;
    else
    { a->etat[i]=nonpris;
      if(a->objetpartiel<0)
       a->optrelax=a->realisable+(capacite-po)*utilite[i]/poids[i], a->objetpartiel=i;
    }
  }
  if (a->objetpartiel<0) a->optrelax=a->realisable;
}
void evalueminpoids(noeud *a)
{ int i, ut=a->realisable=0;
  for(i=0;i<n;i++)         
   if(a->etat[i]==obligatoire)
    a->realisable+=poids[i], ut+=utilite[i];
  a->optrelax=a->realisable;
  for(i=0;i<n;i++)
   if(a->etat[i]<=interdit) ; else
   if(ut>=besoin) a->etat[i]=nonpris; else
   if(a->etat[i]=pris, a->realisable+=poids[i], ut+=utilite[i], ut>=besoin)
     a->optrelax=a->realisable-(ut-besoin)*poids[i]/utilite[i], a->objetpartiel=i;
  if(ut<besoin) a->optrelax=a->realisable+1;
  a->optrelax*=-1;      // pour transformer la minimisation en maximisation
  a->realisable*=-1;
}
void aff(noeud a)
{ if(a.optrelax<a.realisable) printf("pas de solution\n");
  else
  { int i, u=0, p=0;
    for(i=0;i<n;i++) printf("%c","oipn"[a.etat[i]]);
    printf(" %d>=%d %d ",a.optrelax,a.realisable,a.objetpartiel);
    for(i=0;i<n;i++)
     if((a.etat[i]+nonpris)&1) printf(" %d:%d/%d ",i,utilite[i],poids[i]), u+=utilite[i], p+=poids[i];
    printf("  utilite=%d   poids=%d\n",u,p);
  }
}
void resout(void (*evalue)(noeud *a))
{ noeud meilleur={0,0,0};
  void eval(noeud *a)
  { evalue(a);
    if(a->optrelax>=a->realisable && a->realisable>meilleur.realisable) meilleur=*a;
  }
  void separe(noeud a)
  { noeud b=a;
    // aff(a); printf("%3d ",meilleur.realisable); getchar();
    if(a.optrelax<a.realisable || a.optrelax<=meilleur.realisable) return;
    a.etat[a.objetpartiel]=obligatoire;  eval(&a);
    b.etat[b.objetpartiel]=interdit;     eval(&b);
    if(a.optrelax>b.optrelax) separe(a), separe(b);
    else                      separe(b), separe(a);
  }
  int i;
  for(i=0;i<n;i++) meilleur.etat[i]=pris;
  aff(meilleur);
  eval(&meilleur);
  aff(meilleur);
  separe(meilleur);
  aff(meilleur);
}
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);
  resout(evalueminpoids);
  resout(evaluemaxutil );
  return 0;
}