Lab2_Algoritmia_P3_Wood_Cutting

// Uso de DP para el problema Wood Cutting
#include<stdio.h>
#include<limits.h>

// Funcion maximo para sacar 2 enteros
int max(int a, int b) { return (a > b)? a : b;}

/* Retorna el maximo beneficio para una madera de precio[i] por corte [i] */
int cutRod(int price[], int n)
{
   int val[n+1];
   val[0] = 0;
   int i, j;

   // Crea la tabla y usa la tecnica Bottom up

   for (i = 1; i<=n; i++)
   {
       int max_val = INT_MIN;
       for (j = 0; j < i; j++)
         max_val = max(max_val, price[j] + val[i-j-1]);
       val[i] = max_val;
   }

   return val[n];
}

/* Programa principal*/
int main()
{
    int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
    int size = sizeof(arr)/sizeof(arr[0]);
    printf("El máximo valor obtenible es : %d\n", cutRod(arr, size));
    getchar();
    return 0;
}