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;
}
}