Modify the memoizedCutRod method to keep track of the rod length that generates

Question

Modify the memoizedCutRod method to keep track of the rod length that generates the optimal solution for each of the rod lengths used in problem 1 above. • Add a column to the output table to show the optimal rod cut results – the lengths of the rods (after the cuts) that yield the optimal revenue values • The output table should now have these columns with headers: Length , Rev CR, Num Calls CR, Rev MCR, Num Calls MCR, Cut Pieces The output from running the program (after doing problems 1 and 2) should display on the screen as follows: Length Rev CR Num Calls CR Rev MCR Num Calls MCR Cut Pieces 1 1 2 1 2 1 2 5 4 5 4 2 3 8 8 8 7 3 4 10 16 10 11 2 2 5 13 32 13 16 2 3 [The table shows the entire list of results from lengths 1 to 10]

Explanation / Answer

#include<stdio.h>
#include<limits.h>

// A utility function to get the maximum of two integers
int max(int a, int b) { return (a > b)? a : b;}

/* Returns the best obtainable price for a rod of length n and
price[] as prices of different pieces */
int cutRod(int price[], int n)
{
if (n <= 0)
   return 0;
int max_val = INT_MIN;

// Recursively cut the rod in different pieces and compare different
// configurations
for (int i = 0; i<n; i++)
       max_val = max(max_val, price[i] + cutRod(price, n-i-1));

return max_val;
}

/* Driver program to test above functions */
int main()
{
   int arr[] = {1, 5, 8, 9, 10, 17, 17, 20};
   int size = sizeof(arr)/sizeof(arr[0]);
   printf("Maximum Obtainable Value is %d ", cutRod(arr, size));
   getchar();
   return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.