Question
JAVA PROGRAM
Create a class called RodCuttingProblem. This class should have the followings:
JAVA PROGRAM Create a class called RodCuttingProblem. This class should have the followings: a?c A method called cutRod that performs the cutting rod algorithm (without memoization) to compute the optimal revenue value A c Methods called memoizedCutRod and memoizedCutRodAux that perform the cutting rod algorithm (using the memoization technique) to compute the optimal revenue value a?c Each technique should implement a counter to count how many times the method is called (recursively) to solve a problem of rod length a?c Test these algorithms in the main method, using the pricing table shown below a?c Calculate the optimal revenue figures for rods of lengths = 1,2,3 ,?,10, using both methods a?c Your outputs should be a table that shows the following data and results: length , optimal rev from the cutRod (CR) method, number for times the cutRod method is called to solve the problem of length , optimal rev from the memoizedCutRod (MCR) method, number for times the method is called to solve the problem of length a?c The output table should have these columns with headers: Length , Rev CR, Num Calls CR, Rev MCR, Num Calls MCR a?c Compare the results from the cutRod and the memoizedCutRod methods
Explanation / Answer
{ int r[10], s[10], q=0,
class RodCuttingProblem {
int ctr=0;
public void cutRod(p,r)
r[0] = 0;
ctr1++;
for(j=0;j<n;j++)
{ for (i = 0; i < j, i++)
{ if (q < p(i) + r(j-i))
{ q = p(i) + r(j-i) ;
s(j) = i ; // Remember the value of best so far value of i
}
}
return(r,s)
} /// cut rod method
public memoizedCutRod(p,n)
{
}
}
REference ::
Rod Cutting: Bottom Up Solution
Top-Down Solution Observe the following:
i 0 1 2 3 4 5 6 7 8 ri 0 1 5 8 10 13 17 18 22 si 0 1 2 3 2 2 6 1 2
