Consider the following variant of the Rod Cutting problem As

Consider the following variant of the Rod Cutting problem. As we cut the rod. it becomes weaker, so we can only make k greater than n cuts, where n is the length of the rod. Thus now k, n and the price array P[1: n] are inputs to the problem. Give an efficient dynamic programming solution for this problem, and analyze its running time.

Solution

There can be n-1 cuts can be made in the rod of length n, so there are 2n-1 ways to cut the rod.

So for every length we have 2 options either we cut it or not. we will con­sider both the options and choose the opti­mal out of it

Code:

public static int profit(int[] value, int length) {

                                if (length <= 0)

                                                return 0;

                                                // either we will cut it or don\'t cut it

                                                int max = -1;

                                                for(int i=0;i<length;i++)

max = Math.max(max, value[i] + profit(value, length i+1)));                                     

                                                return max;                       

                }

Time Complexity: O(2^n-1)

But this time complexity is very high since we are solving many sub problems repeatedly.