I not getting correct output for cut rod aux algorithm implementation, I am using visual studio 2010 for implementation of Memoized Cut rod aux function....
int max_val=0;
int max(int a, int b)
{
return(a>b)?a:b;
}
int cut_rod_aux(int, int, int);
int cut_rod(int, int);
Most probably error is in this section of code
int cut_rod_aux(int price[], int n, int r[])
{
if(r[n]>=0)
{
return r[n];
cout<<"aux r="<<r<<endl;
}
if (n==0)
{
max_val=0;
cout<<"aux max val = 0"<<endl;
}
else
{
max_val = 0;
for(int i=1; i<n;>
{
max_val=max(max_val, price[i]+cut_rod_aux(price, n-i,r));
cout<<"aux max val: "<<max_val<<endl;
}
}
r[n]=max_val;
return max_val;
}
int cut_rod(int price[], int n)
{
int *r = new int[n];
for(int i=0; i<n;> {
r[i]=0;
cout<<"i="<<i<<" r="<<r[i]<<endl;
}
return cut_rod_aux(price,n,r);
}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[]={1, 5, 8, 9, 10, 17, 17, 20};
cout<<"output "<<cut_rod(arr, 8)<<endl;
return 0;
}
What I have tried:
The correct output should be 22, instead it is giving 20...