# Rod Cutting problem

Input: A rod on X inches. Price list of Rod prices on n inches.

Problem: Cut a rod of X inches into pieces so that it can be sold at a maximum price.

Example

Input- 8 inch rod
Price list : 1 inch piece=1 Rs, 2=5, 3=8, 4=9, 5=10, 6=17, 7=17 and so on

Output= maximum price=22 (6+2 inch)

``` /** * Problem definition: we need to calculate max revenue that can be generated by cutting * a rod of given size (in inches) * @author kamal * */ public class CutRod {```

//we will be given price based on an inch, 0 inch=0Rs, 1=1, 2=5 and so on
//append zeros where price is not known, so here we can sell max rod of 7 inches
private int prices[]={0,1,5,8,9, 10,17,17,0,0,0,0,0,0,0,0,0};//append n

//using dynamic programming, we will store any previously calculated max prices
private int revenue[]=new int;

/**
* Main Method
* @param s
*/
public static void main(String s[])
{
CutRod cr=new CutRod();
System.out.println(cr.fetchMaxPrice(8));
}

``` ```

``` /** * Recursively calls itself to fetch max price * @param size * @return */ private int fetchMaxPrice(int size) { int price=0; if(size==0) return 0; if(revenue[size]>0) return(revenue[size]); //brute force for(int i=1;i<=size;i++) ```

` {`

``` //ith cut price ```

``` price=getMax(price, prices[i]+this.fetchMaxPrice(size-i));```

` revenue[size]=price;`

``` } ```

` return price;`

``` } ```

``` /** * Returns maximum of 2 integers * @param a * @param b * @return */ ```

``` private int getMax(int a, int b) { ```

``` if (a>=b) return a; else return b; } } ```