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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
              // 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 !! :)


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

    ReplyDelete