#include<stdio.h>
#define n 7
#if 0
int p[]={ 3, 4, 2, 4, 3, 1, 4},
    u[]={30,36,16,28,18, 5,16}, P=12;
#else
int p[]={ 7, 4, 5, 9, 4, 7, 3},
    u[]={35,22,26,34,19,33,16}, P=20;
#endif
typedef struct { enum {inter,oblig,nonpr,pris} t[n]; int mi,ma,sep; } noeud;
noeud opt;
void aff(noeud a)
{ int i;
  for(i=0;i<n;i++) printf("%c","IONP"[a.t[i]]);
  printf(" %d %d %d\n",a.mi,a.ma,a.sep);
}
void eval(noeud *a)
{ int su=0, sp=0, i;
  a->sep=-1; // On n'a pas encore trouvé l'objet qui fait déborder le sac. 
  // On calcule la somme des utilités et des poids des objets imposés.
  for(i=0;i<n;i++) if(a->t[i]==oblig) { su+=u[i]; sp+=p[i]; }
  if(sp>P) { a->ma=-1; return; }  // Le sac déborde déjà avec les objets imposés.
  for(i=0;i<n;i++) if(a->t[i]> oblig)
  { if(sp+p[i]<=P) { su+=u[i]; sp+=p[i]; a->t[i]=pris; } else
    { a->t[i]=nonpr;
      if(a->sep==-1) { a->sep=i; a->ma=su+u[i]*(P-sp)/p[i]; }
    }
  }
  a->mi=su;   
  if(a->sep==-1) a->ma=su; // Tous les objets tiennent dans le sac.
  if(su>opt.mi) opt=*a;
  if(1) printf("fin de eval "),aff(*a);
}
void traite(noeud *a)
{ if(a->ma<=opt.mi) return;
  noeud b=*a, c=*a;
  b.t[b.sep]=oblig; eval(&b);
  c.t[c.sep]=inter; eval(&c);
  if(b.ma>c.ma) traite(&b), traite(&c);
  else          traite(&c), traite(&b);
}
int main()
{ int i,j,x;
  for(i=0;i<n;i++) opt.t[i]=nonpr;
  for(i=n;i--;) for(j=0;j<i;j++) if(u[i]*p[j]>u[j]*p[i])
  { x=u[i], u[i]=u[j], u[j]=x,  x=p[i], p[i]=p[j], p[j]=x; }
  for(i=0;i<n;i++) printf("%d/%d=%.5f ",u[i], p[i], u[i]*1./p[i]);
  printf("\n");
  opt.mi=0;
  eval(&opt);
  traite(&opt);
  aff(opt);
  return 0;
}