**Problem Statement:**

Given a Rod of length n inches , and table of prices for each rod length starting from 1 till n. Find the solution to the cut the rod such that maximum revenue is generated if sold.

Fig: Table : Length and Price |

**Solution :**

The rod can be cut in 2

^{(n-1)}ways for length n , below are the shown combinations for n=4

Fig: All Possible Combinations for n=4 |

We will have to opt Dynamic Programming which will reduce repeated calculation of sub-problems again and again if recursion was used. In case of dynamic programming we will store the data of the sub-problems computed and will use them for bigger problem which include these sub-problems.

Time complexity of recursive solution : O(2

^{n})^{}

Below is the maximum revenue generated for each length for the above problem with n=9, which is computed from the sub-lengths.

With Dynamic Programming(DP) , we will be solving a sub-problem and store that, there are two approaches with storage of values:

a) Top - Down Memoized* Solution

b) Bottom-Up Solution

**Note :**Memoized is the correct spelling, as we write a Memoized comes from memo, since this technique consists of storing of values.

We will be discussing the Bottom-Up Solution below,

In this technique we solve the smaller sub-problems first, when we arrive at the actual problem whose solution depends on smaller sub-problems , and solution of smaller sub-problems is already stored.

**Full Source Code : LINK**

// Auxillary array to hold maxCost for each length private int[] aux; private int[] cost; // used to find length of stick private int sol[]; /** * Bottom up Approach * @param cost : cost of sticks * @param len : given length * @return : maximum revenue for given length */ public int bottomUp(int cost[],int len){ aux[0] = 0; //auxillay array int maxCost = 0; for(int i=1;i<=len;i++){ maxCost=Integer.MIN_VALUE; for(int j=0;j<i;j++) if(maxCost < cost[j] + aux[(i-1)-j]){ maxCost = cost[j] + aux[(i-1)-j]; sol[i] = j+1; } aux[i]=maxCost; } return maxCost; } private void printSol(int len){ while(len > 0){ System.out.print(sol[len] + "\t"); len=len - sol[len]; } }

I have given code for Bottom up approach , users can try Top-Down approach and can refer to the below references.

Reference: http://users.csc.calpoly.edu/~dekhtyar/349-Spring2010/lectures/lec09.349.pdf and Cormen

Please feel free to comment , any critique or suggestion is most welcome.

Happy Coding !! :)

If you desire to improve your know-how only keep visiting this web page and be updated with the latest gossip posted here.

ReplyDeletemy blog :: Transformers Age of Extinction Hack ()