#include <stdio.h>
#define N 5
#define S 10
#define infini 10000

const int alpha[N+1] = {0,5,8, 6,7,6}, // coût de production d'un objet pendant un mois
          X    [N+1] = {0,3,7, 6,5,4}, // nombre maximal d'objets produits durant le mois
          D    [N+1] = {0,1,2,10,3,6}, // demande (nombre d'objets à fournir)
          H    [N+1] = {0,1,2, 2,1,2}; // coût de stockage d'un objet en fin de mois
          
int main ()
{   int f[N+1][S+1], i, t, M, y, K, sim ;
    f[0][0] = 0;                       // coût nul pour un stock nul au début du premier mois
    for (t=1 ; t<=S ; t++) f[0][t] = infini ;  // au début du premier mois, le stock ne peut pas être non nul
    for (i=1 ; i<=N ; i++)             // i est le numéro du mois  
    for (t=0 ; t<=S ; t++)             // t est le stock à la fin du mois i
    {
         M = infini;                   // initialisation pour le calcul d'un minimum
         for (y=0 ; y<=X[i] ; y++)     // y est le nombre d'objets produits pendant le mois i
         {
              sim = t - y + D[i] ;     // sim est le stock en début de mois (Le stock passe de sim à t )
              if (sim<0 || sim>S) continue ;  // stock trop petit ou trop grand. On passe au y suivant
              K = f[i-1][sim] + alpha[i]*y + H[i]*t ; // coût minimal pour que le stock passe de sim à t le mois i
              if (K<M) M=K ;           // On garde le plus petit coût trouvé
         }
         f[i][t] = M;                  // plus petit coût possible pour avoir un stock t à la fin du mois i
    }
    // affichage   du tableau f
    for (t=0 ; t<=N ; t++)
    {
        printf("\n");
        for (i=0 ; i<=N ; i++) printf("%6d", f[i][t]);
    }
    // recherche de la solution optimale
    printf("\n");
    { int  s[N+1], x[N+1];
      s[N]=0;
      for(i=N;i;i--)
      {  t=s[i];
         for (y=0 ; y<=X[i] ; y++)
         { 
              sim = t - y + D[i] ;
              if (sim<0 || sim>S) continue ;
              K = f[i-1][sim] + alpha[i]*y + H[i]*t ;
              if(f[i][t]==K) s[i-1]=sim, x[i]=y;
         }
      }
    // affichage de la solution optimale
      x[0]=0;
      for(i=0;i<=N;i++) printf("%6d",x[i]);   printf("  production\n");
      for(i=0;i<=N;i++) printf("%6d",s[i]);   printf("  stock\n");
    }
    getchar();
    return 0;
}
/*
     0     5    17    93   114   154
 10000    11    27   105   122   169
 10000    17    37   117   130   184
 10000 10000    47   129   143   199
 10000 10000    57 10000   156 10000
 10000 10000    67 10000   169 10000
     0     3     4     6     5     4  production
     0     2     4     0     2     0  stock
*/