8 Nov 2013

Rod Cutting problem

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
 The Greedy Approach won't give the correct answer to this problem.
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(2n)

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++){

   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;

  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 !! :)

1 comment:

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

    my blog :: Transformers Age of Extinction Hack ()