#include<stdio.h>
#define n 4
int deb[n]={ 1, 0, 7, 9},  // date de début de tâche au plus tôt
    fin[n]={ 4, 6,13,12},  // date de fin de tâche au plus tard
    dur[n]={ 3, 2, 2, 3},  // durée de la tâche
    cou[n]={ 7, 4, 4, 7};  // pénalité si la tâche n'est pas faite dans les limites de temps
typedef struct{int min,    // évaluation par défaut : somme des pénalité des tâches ne pouvant plus être faites à temps
                   maj,    // évaluation par excès : somme des pénalité des tâches non fixées
                   fin,    // date de fin de la dernière des tâches fixées
                   deb[n]; // date de début des tâches fixées, -1 pour les tâches non fixées 
              } noeud;
noeud h;
int min(int a,int b) {return a<b?a:b;}
int max(int a,int b) {return a>b?a:b;}
void eval(noeud *a)
{ int i;
  a->maj=a->min=0;
  for(i=0;i<n;i++) if(a->deb[i]<0)                       // le coût de chaque tâche i non fixée
  { a->maj+=cou[i];                                      //   est ajouté a l'évaluation par excès  
    if(max(deb[i],a->fin)+dur[i]>fin[i]) a->min+=cou[i]; //   et à l'évaluation par défaut si elle ne peut pas être
  }                                                      //    faite à temps après la date fin   
  if(a->maj<h.maj) h=*a;                                 // h est la meilleure solution réalisable trouvée jusqu'ici 
}
void separe(noeud *a)
{ noeud t[n],u;
  int i,j,m,x;                           
  for(i=m=0;i<n;i++) if(a->deb[i]<0)     // On sépare en choisissant une des tâches i non fixées 
  { t[m]=*a;
    t[m].deb[i]=x=max(a->fin,deb[i]);    // qui sera exécutée le plus tôt possible après la date a->fin
    t[m].fin=x+=dur[i];                  // date de fin de cette tâche
    if(x<=fin[i]) eval(t+m++);           // Si cette tâche peut être faite à temps, on garde ce noeud et on l'évalue
  }
  for(i=m;i--;)                          // On trie les fils de *a dans l'ordre croissant des évaluations par défaut
  for(j=0;j<i;j++)                       
  if(t[j].min>t[j+1].min) u=t[j], t[j]=t[j+1], t[j+1]=u;
  for(i=0;i<m;i++) if(t[i].min<h.min) separe(t+i); // On les traite un par un dans cet ordre
}
void aff(noeud *a)
{ int i;
  for(i=0;i<n;i++) if(a->deb[i]>=0) printf(" %d:%d->%d",i,a->deb[i],a->deb[i]+dur[i]);
                   else             printf(" %d:(%d)",i,cou[i]);
  printf("   %d\n",a->maj);
}
void sepeval()
{ int i;
  for(i=0;i<n;i++) h.deb[i]=-1;  // Aucune des tâches n'est fixée
  h.fin=0;                       // On peut commencer l'exécution des tâches à la date 0.
  eval(&h);                      // Dès qu'un noeud est créé, il faut l'évaluer
  separe(&h);                    // Parcours récursif en profondeur d'abord de l'arbre
  aff(&h);                       // Affichage de la solution optimale
}
void dyna()
{ int nn=1<<n, // 2 puissance n  est le nombre de parties de l'ensemble {0,1,...,n-1}
      i,J,Jm=0,Ji,infini=0,
      FIN[nn], // FIN[J] est la date de fin au plus tôt de l'exécution de toutes les tâches de l'ensemble J
      cc[nn];  // cc[J] est la somme des pénalités de tâches qui sont dans J
  for(i=0;i<n;i++) infini=max(infini,fin[i]), cc[1<<i]=cou[i];  // cc[{i}]=cou[i]
  infini++;                                                     // infini = 1+ la plus grande date de fin
  for(J=0;J<nn;J++) FIN[J]=infini;
  FIN[0]=cc[0]=0;
  for(J=0;J<nn;J++)
  { cc[J]=cc[J&-J]+cc[J&(J-1)];           // cc[{2,3,6}]=cc[{2}]+cc[{3,6}]
    if(FIN[J]==infini) continue;          // on ne peut pas faire toutes les tâches de J dans les temps
    if(cc[J]>cc[Jm]) Jm=J;                // Jm est l'ensemble de tâches réalisables à temps qui maximise cc
    for(i=0;i<n;i++) if(Ji=J^(1<<i),Ji>J) // Ji=J u{i}   donc Ji>J <=> i n'est pas dans J
    { int x=max(FIN[J],deb[i])+dur[i];       // date de fin de la tâche i exécutée dès que possible après toutes les tâches de J
      if(x<=fin[i] && x<FIN[Ji]) FIN[Ji]=x;  // si elle est dans les temps, x est une valeur possible pour FIN[J u{i}]
    }
  }
  for(Ji=Jm;Ji;Ji=J)                  // On retrace à l'envers l'origine du nombre F[Jm]       
  { for(i=0;i<n;i++) if(J=Ji^(1<<i), J<Ji && FIN[Ji]<=fin[i] && FIN[Ji]==max(FIN[J],deb[i])+dur[i]) break;
    printf(" %d:%d->%d",i,FIN[Ji]-dur[i],FIN[Ji]);
  }
  for(i=0;i<n;i++) if(~Jm&(1<<i)) printf(" %d:(%d)",i,cou[i]);  // on affiche les tâches non exécutées et leur coût
  printf("   %d\n",cc[nn-1]-cc[Jm]);                            // coût total des tâches non exécutées
}
int main()
{ sepeval();
  dyna();
  dur[2]=3;
  sepeval();
  dyna();
  return 0;
}