**13**

*Jul*

*2018*

### Cutting Rod Problem to get maximum profit

You are given a rod of a particular length and prices at which those different lengths of this rod can be sell, how will you cut this rod to maximize your profit?

We will be using dynamic programming to solve this problem. Java Solution for the problem is given below:

```
import java.util.HashMap;
public class CuttingRodProblem {
private static int max(int a, int b) {
return a>b?a:b;
}
public static void main(String[] args) {
//adding extra 0 in beginning as dummy value.
Integer[] rodLenArr = new Integer[] {0, 1, 2, 3, 4};
Integer length = 5;
HashMap<Integer,Integer> profit = new HashMap<Integer,Integer>();
profit.put(rodLenArr[0], 0);
profit.put(rodLenArr[1], 2);
profit.put(rodLenArr[2], 5);
profit.put(rodLenArr[3], 7);
profit.put(rodLenArr[4], 8);
Integer[][] dp = new Integer[rodLenArr.length+1][length+1];
for(int i=0;i<rodLenArr.length;i++) {
for(int j=0;j<length+1;j++) {
if(j==0 || i == 0)
dp[i][j]=0;
else if(j<rodLenArr[i]) {
dp[i][j]=dp[i-1][j];
}
else {
dp[i][j]=max(dp[i-1][j],
dp[i][j-rodLenArr[i]]
+profit.get(rodLenArr[i]));
}
}
}
System.out.println(dp[rodLenArr.length-1][length]);
}
}
```

Time Complexity of the above solution will be n*m. Where n is the total number of different lengths of the rod while m is the length of the given rod.