#define maxcam 4 #define maxcuivre 250 #define maxcarb 200 #define reservoir 2 #define charge 40 #define achatcam 50000 #define achatcuivre 100 #define achatcarb 100 #define vendecam 48800 #define vendecuivre 500 #define distance 10 int TAB[distance+1][maxcarb+1][maxcam+1][maxcuivre+1]; void initialise() { int cuivre,cam,carb; for (carb=0;carb<=maxcarb;carb++) for (cuivre=0;cuivre<=maxcuivre;cuivre++) for (cam=0;cam<=maxcam;cam++) { TAB[distance][carb][cam][cuivre]=cam*vendecam+cuivre*vendecuivre; } } void remplir() { int d,carb,cuivre,cam; for (d=distance-1;d>=0;d--) for (cuivre=0;cuivre<=maxcuivre;cuivre++) for (carb=0;carb<=maxcarb;carb++) for (cam=1;cam<=maxcam;cam++) { int opt=0, alt; /*printf("calcul de TAB[%i,%i,%i,%i]",d,carb,cam,cuivre);*/ if (carb>0) { alt=TAB[d][carb-1][cam][cuivre]; if (alt>opt) opt=alt; } if (cam>0) { alt=TAB[d][carb][cam-1][cuivre]; if (alt>opt) opt=alt; } if (cuivre>0) { alt=TAB[d][carb][cam][cuivre-1]; if (alt>opt) opt=alt; } {int t2=(cuivre+charge-1)/charge, t3=(cuivre+carb+charge+reservoir-1)/(charge+reservoir), t=t2>t3?t2:t3, u=t>cam?2*t-cam:cam; if (carb>=u) {alt=TAB[d+1][carb-u][cam][cuivre]; if (alt>opt) opt=alt; } } TAB[d][carb][cam][cuivre]=opt; /*printf(" optimum=%i\n",opt);*/ } } void tracepath(int d, int cam, int carb, int cuivre) {int vente=TAB[d][carb][cam][cuivre]; printf("meilleur politique en position %i avec %i camions, %i bidons et %i sacs\n", d, cam, carb, cuivre); if (d==distance) {printf("Vendre tout\n");return;} if (carb>0 && TAB[d][carb-1][cam][cuivre]==vente) {printf("jeter 1 bidon \n"); tracepath(d,cam,carb-1,cuivre);return;} if (cuivre>0 && TAB[d][carb][cam][cuivre-1]==vente) {printf("jeter 1 sac de cuivre\n");tracepath(d,cam,carb,cuivre-1);return;} if (cam>1 && TAB[d][carb][cam-1][cuivre]==vente) {printf("jeter 1 camion\n");tracepath(d,cam-1,carb,cuivre);return;} printf("transporter tout\n"); {int t2=(cuivre+charge-1)/charge, t3=(cuivre+carb+charge+reservoir-1)/(charge+reservoir), t=t2>t3?t2:t3, u=t>cam?2*t-cam:cam; if (carb>=u) if (TAB[d+1][carb-u][cam][cuivre]==vente) { tracepath(d+1,cam,carb-u,cuivre); return; } } printf("error\n"); } void findbest() {int carb,cam,cuivre,opt=0,optcarb,optcam,optcuivre; for (carb=0;carb<=maxcarb;carb++) for (cam=0;cam<=maxcam;cam++) for (cuivre=0;cuivre<=maxcuivre;cuivre++) {int benefice=TAB[0][carb][cam][cuivre]- (cuivre*achatcuivre+cam*achatcam+carb*achatcarb); if (benefice>opt) {opt=benefice; optcarb=carb; optcam=cam; optcuivre=cuivre; } } printf("Meilleur resultat: %i avec %i camions et %i sacs utilisant %i bidons\n", opt, optcam, optcuivre, optcarb); tracepath(0, optcam, optcarb, optcuivre); } int main() { initialise(); remplir(); findbest(); }