WRITE A FUNCTION IN MATLAB Function Name: cutTheRope Inputs: 1. (double) A 1xN v

Question

WRITE A FUNCTION IN MATLAB

Function Name: cutTheRope

Inputs: 1. (double) A 1xN vector of integers representing rope turns

Outputs: 1. (double) The location that cuts the rope into the most pieces 2. (double) The maximum number of pieces

Function Description If you loved the game Cut the Rope, then try to contain your excitement apart from the name, this problem has nothing to do with that game. Imagine you have a rope that zigzags along a number line with the locations of the corners defined by the integers in the input to the function. You must calculate the location along the number line where you can make a vertical cut to break the rope into the maximum number of pieces. The rope will always turn at integer values (there would never be a turn at 3.45, for example). Additionally, you are only allowed to cut the rope halfway between integers (at 1.5, 2.5, 4.5, etc). It may be the case that any cut on a particular range (or multiple disjoint ranges) will produce the same number of pieces. In this case, you should output the smallest cut location that will produce the maximum number of pieces. For example, if cutting the rope anywhere between 2 and 5 or between 7 and 8 would produce 10 pieces, and this is the maximum number of pieces, then you should output 1.5 as the cut location because this is the smallest number on these ranges that lies halfway between 2 integers.

Example:

Consider the following example:
An input of: [2, 3, 1, 3, 1, 0, 1, 3, 1]
would represent a rope that zigzags
in the following way:
Any cut on the range (1, 3) will produce the maximum number of pieces (7), but because we
must cut the rope at the smallest location on this range that is halfway between integers, the cut
location would be 1.5. Therefore the first output for this case (cut location) would be 1.5 and the
second output (maximum number of pieces) would be 7, as visualized by the next plot:
To help you visualize any test case, we have provided a function called cutTheRope

Explanation / Answer

// A Naive recursive solution for Rod cutting problem

#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;

}

Run on IDE

Output:

Considering the above implementation, following is recursion tree for a Rod of length 4.

In the above partial recursion tree, cR(2) is being solved twice. We can see that there are many subproblems which are solved again and again. Since same suproblems are called again, this problem has Overlapping Subprolems property. So the Rod Cutting problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array val[] in bottom up manner.

// A Naive recursive solution for Rod cutting problem

#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 W
• Subjects

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