#include <stdio.h>

int sac2(int n, int P, int Q, int p[], int u[], int t[])
{ int f[n+1][P+1][Q+1], i, R, S;
  // f[i][R][S] est l'utilité maximale que l'on peut obtenir en choisissant des objets parmi les i premiers,
  // et en les répartissant dans deux sacs de capacité R et S.
  for(R=0;R<=P;R++)
  for(S=0;S<=Q;S++) f[0][R][S]=0;  // On n'a droit à aucun objet, donc les sacs sont vides et d'utilité nulle.
  for(i=0;i< n;i++)
  for(R=0;R<=P;R++)
  for(S=0;S<=Q;S++)
  { int x=f[i][R][S], y;                              // On ne prend pas l'objet i.
    if(R>=p[i] && (y=f[i][R-p[i]][S]+u[i])>x) x=y;    // On le met dans le premier sac, s'il y rentre et que cela permet d'augmenter l'utilité.
    if(S>=p[i] && (y=f[i][R][S-p[i]]+u[i])>x) x=y;    // On le met dans le deuxième sac éventuellement.
    f[i+1][R][S]=x;
  }
// On va chercher comment on a obtenu le nombre f[n][P][Q]
  for(i=n,R=P,S=Q;i--;)                               // On cherche comment on a obtenu le nombre f[i+1][R][S]
  t[i]= R>=p[i] && f[i][R-p[i]][S]+u[i]==f[i+1][R][S] ? R-=p[i],1 : // L'objet i est dans le sac 1
        S>=p[i] && f[i][R][S-p[i]]+u[i]==f[i+1][R][S] ? S-=p[i],2 : // L'objet i est dans le sac 2
                                                                0;  // L'objet i n'est pas pris.
  return f[n][P][Q]; 
}

int main()
{ int n=4, p[]={4,5,6,7}, u[]={3,8,5,9}, P=10, Q=7, t[n], U=sac2(n,P,Q,p,u,t), i;
  printf("U=%d\n",U);
  for(i=0;i<n;i++) printf("%d,%d,%d  ", p[i], u[i], t[i]);
  printf("\n");
  return 0;
}