# 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[20]; /** * 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; } } ```