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.


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

* Recursively calls itself to fetch max price
* @param size
* @return
private int fetchMaxPrice(int size)
int price=0;
return 0;
//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;
return b;