Question

Q(1) Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters Examples: (n-4) Input: rope length is 4 Output: 2*2-4(Maximum obtainable product is 2*2) Input: rope length is 5 Output: 2*3-6 (Maximum obtainable product is 2*3) (n-5) Input: rope length is 10 (n- 10) Output: 3*3*4-36 (Maximum obtainable product is 3*3*4) a) Design the recursive sub-problem condition(s) b) Use your solution in (a) to solve the problem of a rope length input equals 10 (n = 10). You have to show the complete solution of the DP steps either by top down or bottom-up approach. c) What is the running time of your algorithm?

Answer 1

ANS:-

CODING TO TRY..

// Using Recursive method to find maxium product

#include <iostream.h>

// Function to get the maximum of two and three integers

int max(int a, int b) { return (a > b)? a : b;}

int max(int a, int b, int c) { return max(a, max(b, c));}

// Returns maximum product obtainable from a rope of length n

int Maxproduct(int n)

{

    // cases considered only for rope length greater than 2

    if (n == 0 || n == 1) return 0;

    // Make a cut at different places and take the maximum of all

    int MaximumValue = 0;

    for (int i = 1; i < n; i++)

      MaximumValue = max(MaximumValue, i*(n-i), Maxproduct(n-i)*i);

    // Return the maximum of all values

    return MaximumValue;

}

/* Main Program */

int main()

{

    cout << "Maximum Product is " << Maxproduct(10);

return 0;

}