#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define N 3
#define INFINITY 1000000000
#define T 5
#define min(a, b) (((a) < (b)) ? (a) : (b))
int p[N] = {3, 6, 4};
int s[N] = {2, 3, 7};
int cost(int i, int t){
printf ("%*c inizio cost con i = %d, t = %d \n", N-i, ' ', i, t);
if (t <= 0) {
printf("%*c t <= 0, return 0 \n", N-i, ' ');
return 0;
}
if (i < 0) {
printf("%*c i < 0, return inf \n", N-i, ' ');
return INFINITY;
}
int a, b;
printf("%*c chiamo cost con scelta giocatore \n", N-i, ' ');
a = p[i] + cost(i - 1, t - s[i]);
printf("%*c totale costo con scelta giocatore: %d \n", N-i, ' ', a);
printf("%*c chiamo cost senza scelta giocatore \n", N-i, ' ');
b = cost(i - 1, t);
printf("%*c totale costo senza scelta giocatore: %d \n", N-i, ' ', a);
if (a < b) {
printf("%*c return a: %d\n", N-i, ' ', a);
return a;
} else {
printf("%*c return b: %d\n", N-i, ' ', b);
return b;
}
}
int main()
{
int c;
c = cost(N - 1, T);
printf("costo minimo: %d\n", c);
// Metodo bottom-up
int *C = malloc(sizeof(int) * (N + 1));
int *D = malloc(sizeof(int) * (N + 1));
printf("C[0, 0] = 0\n");
C[0] = D[0] = 0;
for (int t = 1; t <= T; ++t) {
printf("C[0, %d] = %d\n", t, INFINITY);
C[t] = D[t] = INFINITY;
}
for (int i = 0; i < N; ++i) {
printf("C[%d, 0] = 0\n", i + 1);
D[0] = 0;
for (int t = 1; t < s[i]; ++t) {
D[t] = min(p[i], C[t]);
printf("C[%d, %d] = min(p_%d = %d, C[%d, %d] = %d) = %d\n",
i + 1, t, i + 1, p[i], i, t, C[t], D[t]);
}
for (int t = s[i]; t <= T; ++t) {
D[t] = min(p[i] + C[t - s[i]], C[t]);
printf("C[%d, %d] = min(p_%d + C[%d, %d] = %d, C[%d, %d] = %d) = %d\n",
i + 1, t, i + 1, i, t - s[i], p[i] + C[t - s[i]], i, t, C[t], D[t]);
}
int *tmp = C;
C = D;
D = tmp;
}
printf("costo minimo: %d\n", C[T]);
free(D);
free(C);
return 0;
}
