#include "stdio.h"
#include "stdlib.h"

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

/**
* Détermine le cout minimal du cout de production et du cout de stockage
* satisfaisant la demande des commandes passées sur les n prochains jours.
* n     : Nombre de jours
* Emax  : Stockage maximale possible                        max(E)
* d[]   : Demande selon le jour i                           Di
* q[]   : Quantité de production maximale selon le jour i   Qi
* t[]   : Cout de stockage unitaire selon le jour i         Ti
* c[]   : Cout de production unitaire selon le jour i       Ci
*/
int cout_min(int n, int d[], int q[], int t[], int c[]) {
    int Emax=0, e=0, k, x, ee;
    for(k=0;k<n;k++) Emax=max(Emax,e+=q[k]-d[k]);
    unsigned int f[n+1][Emax+1];

    for(k=0;k<=n;k++) for(e=0;e<=Emax;e++) f[k][e]=~0u/2;
    f[0][0]=0;
    for(k=0;k<n;k++) for(e=0;e<=Emax;e++) for(x=0;x<=q[k];x++)
    if(ee=e+x-d[k],ee>=0 && ee<=Emax) f[k+1][ee]=min(f[k+1][ee],f[k][e]+x*c[k]+ee*t[k]);
    
    for(ee=0,k=n;k--;printf("%2d  %2d=%2d+%2d*%2d+%2d*%2d  %2d=%2d+%2d-%2d\n",k,f[k+1][ee],f[k][e],x,c[k],ee,t[k],ee,e,x,d[k]),ee=e)
    for(x=0;x<=q[k];x++) if(e=ee-x+d[k],e>=0) if(f[k+1][ee]==f[k][e]+x*c[k]+ee*t[k]) break;

    return f[n][0];
}


int main(int argc, char const *argv[]) {
    int n = 6;
    int d[] = { 5,  6,  6,  4,  5,  7};
    int q[] = {10, 10, 10, 10, 10, 10};
    int c[] = { 3,  1,  2,  3,  1,  5};
    int t[] = { 2,  2,  1,  2,  2, 10};
    int cout = cout_min(n, d, q, t, c);
    printf("Cout min %d\n", cout);
    return 0;
}