Write a recurrence that would be used in dynamic programming for the following problem: Given a rod of length n and an array A of prices that contain all prices of all the pieces smaller than n. Determine the maximum value obtained by cutting up the rod and selling the pieces. Note that you could sell the rod at its original length without cutting it.
Write a recurrence that would be used in dynamic programming for the
following problem: Given a rod of length n and an array A of prices that
contain all prices of all the pieces smaller than n. Determine the maximum
value obtained by cutting up the rod and selling the pieces. Note that you
could sell the rod at its original length without cutting it.
#include<stdio.h>
#include<limits.h>
// this is mainly used for the finding of two integers that is maximum
int max(int x, int y) { return (x > y)? x : y;}
int cutRod(int p[], int k)
{
if (k <= 0)
return 0;
int max_val = INT_MIN;
// the rod is cut into several pieces and the configuration is being calculated
for (int i = 0; i<k; i++)
max_val = max(max_val, p[i] + cutRod(p, k-i-1));
return max_val;
}
int main()
{
int a[] = {1, 5, 8, 9};
int s = sizeof(a)/sizeof(a[0]);
printf("Maximum value obatined is %dn", cutRod(a, s));
getchar();
return 0;
}
Step by step
Solved in 2 steps with 1 images
