#include<stdio.h>
#include<stdlib.h>
#define n 5
const int a[n+1]={0,3,4,5,4,3},  // durée de la tâche i sur la première machine
          b[n+1]={0,6,3,7,2,4},  // durée de la tâche i sur la deuxième machine
          c[n+1]={0,4,8,3,5,2};  // montant de la pénalité si la tâche i n'est pas faite dans la journée
#define J 7
int main()
{ int F[n+1][J+1][J+1], k,A,B,x,y;
  for(A=0;A<=J;A++) for(B=0;B<=J;B++) F[n][A][B]=A>=a[n] || B>=b[n] ? 0 : c[n];
  for(k=n;--k>0;) for(A=0;A<=J;A++) for(B=0;B<=J;B++)
  { x=F[k+1][A][B]+c[k];  // on ne fait pas la tâche k
    if(A>=a[k] && (y=F[k+1][A-a[k]][B])<x) x=y;  // on a le temps de faire la tâche k sur la première machine et cela coûte moins cher
    if(B>=b[k] && (y=F[k+1][A][B-b[k]])<x) x=y;  // on a le temps de faire la tâche k sur la deuxième machine et cela coûte moins cher
    F[k][A][B]=x;
  }
  printf("coût total : %d\n",F[1][J][J]);
  { int m[n+1];
    for(k=1,A=B=J;k<n;k++)
    m[k]= A>=a[k] && F[k+1][A-a[k]][B]==F[k][A][B] ? A-=a[k],1 :
          B>=b[k] && F[k+1][A][B-b[k]]==F[k][A][B] ? B-=b[k],2 :
                                                             0 ;
    m[n]= A>=a[n] ? 1 :
          B>=b[n] ? 2 :
                    0 ;
    for(k=1;k<=n;k++) printf("%d:%d ",k,m[k]);
    getchar();
  }
  return 0;
}