#include <stdio.h>
#include <stdlib.h>

int min(int a,int b) { return a<b?a:b; }

int foo(int n, int J, int a[], int b[], int c[])
{   int F[n+1][J+1][J+1], k, A, B;

    //Calcul de F[n][A][B]
    for(A=0;A<=J;A++) for(B=0;B<=J;B++) F[n][A][B]=0;

    //Récurrence
    for(k=n;k--;) for(A=0;A<=J;A++) for(B=0;B<=J;B++)
    { int x=F[k+1][A][B]+c[k];
      if(A>=a[k]) x=min(x,F[k+1][A-a[k]][B]);
      if(B>=b[k]) x=min(x,F[k+1][A][B-b[k]]);
      F[k][A][B]=x;
    }

    //Reconstitution d'une solution optimale
    for (A=B=J,k=0;k<n;k++)
     if(F[k][A][B]==F[k+1][A][B]+c[k]) printf("La tâche %d est rejetée\n", k);
     else if(A>=a[k] && F[k][A][B]==F[k+1][A-a[k]][B])  A-=a[k], printf("La tâche %d est effectuée par la machine 1\n", k);
     else                                               B-=b[k], printf("La tâche %d est effectuée par la machine 2\n", k);
    return F[0][J][J];
}

int main()
{   int a[] = {2, 3, 4, 3, 2, 5},
        b[] = {3, 2, 5, 4, 3, 6},
        c[] = {2, 4, 6, 3, 2, 1}, J=5, n=6, x=foo(n, J, a, b, c);
    printf("coût : %d\n", x);
    return 0;
}