(10) Let us modify the rod-cuting problem by adding the following condition: Cut

Question

(10) Let us modify the rod-cuting problem by adding the following condition: Cutting a rod of length j 2 of the rod. T the pieces minus the sum of the costs incurred for cutting it into these pieces. Design an efficient dynamic programming algorithm for solving this problem and discuss its correctness (exploiting an optimal substructure property) and running time. 2 into two pieces incurs a cost c, that depends on the length j hus the total revenue you get for a rod is now the sum of the prices of

Explanation / Answer

Program is written using dynamic programming.

complexity is explained in comments .

Porgram can be executed in both C and C++ languages.

#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;//this function executes in constant time just based on comparison of one statement
}

// Returns the best obtainable price for a rod of length n and price[] as prices of different pieces
int cut(int price[], int n)
{
int val[n+1];
val[0] = 0;
int i, j;

// Build the table val[] in bottom up manner and return the last entry from the table
for (i = 1; i<=n; i++)//loop executes n times
{
   int max_val = INT_MIN;//initialize minimum value at first
   for (j = 0; j < i; j++)//loop executes based on the value of i as 1 , 2 , 3 .....
   {
       max_val = max(max_val, price[j] + val[i-j-1]);//calling max function
   }
   val[i] = max_val;//storing max value
  
   //so based on the execution of two for loops total loop entries can be added as 1+2+3+.....+n = (n(n+1))/2= (n^2)/2 + (n+1)/2 so for larger values of n , we can neglect (n+1)/2 against (n^2)/2 so overall complexity can be written in the terms of O(n^2)
}
}
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 ", cut(arr, size));
  
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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