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(2ⁿ)

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