Question
I want to Implement Rod cutting Algorithm without Dynamic Programming Approach.
Let me Describe the problem statement.
Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.
In cormen, the Algorithm is implemented as -:
CUT-ROD (p,n)
1 if n == 0
2 return 0
3 q = - inifinity
4 for i = 1 to n
5 q =max(q, p[i]+CUT-ROD(p,n-i))
6 return q
I got this algorithm , i may explain it with a example-:
Say we want to determine maximum revenue for $n=4$,
and the profit associated with each inches i.e $i=1,2,3,4$is given as follows-:
$p[1]=1,p[2]=5,p[3]=8,p[4]=9$
Now Moving to the algorithm ,if we want to find maximum revenue for Length 4 inch ,we need to call CUT-ROD$(p,4)$.How will it process , i mean what will be its sequence!?i can explain-:
CUT-ROD$(p,4)$ will be computed by
maximum value of
- $p[1]+$CUT-ROD$(p,3)$
- $p[2]+$CUT-ROD$(p,2)$
- $p[3]+$CUT-ROD$(p,1)$
- $p[4]+$CUT-ROD$(p,0)$
for $i=1,2,3,4$ respectively.
Now when $i=1$, it will encounter CUT-ROD$(p,3)$
CUT-ROD$(p,3)$ will be computed by
maximum value of
- $p[1]+$CUT-ROD$(p,2)$
- $p[2]+$CUT-ROD$(p,1)$
- $p[3]+$CUT-ROD$(p,0)$
for $i=1,2,3$ respectively.
CUT-ROD$(p,2)$ will be computed by
maximum value of
- $p[1]+$CUT-ROD$(p,1)$
- $p[2]+$CUT-ROD$(p,0)$
for $i=1,2$ respectively.
CUT-ROD$(p,1)$ will be computed by
maximum value of
- $p[1]+$CUT-ROD$(p,0)$
for $i=1$
CUT-ROD$(p,1)$=1,CUT-ROD$(p,2)$=$max(1+1,5)=5$
CUT-ROD$(p,3)$=$max(1+5,5+1,8+0)=8$
CUT-ROD$(p,4)$=$max(1+8,5+5,8+1,9+0)=10$
MY Doubt
I implemented the $C$ code,but it is giving wrong result.I don't know why!
I guess that the sequence of the function call is wrong .Here is the code.
#include<stdio.h>
int p[100];
int result=-9999;
int count=0;
int max(int x,int y)
{
return (x > y)? x : y;
}
int recrsv_top_down(int sizee)
{
int i;
if (sizee<=0)
{
return 0;
}
for(i=1;i<=sizee;i++)
{
result=max(result,(p[i]+(recrsv_top_down(sizee-i))));
}
return result;
}
int main()
{
int size,i,result;
printf("enter the size of rod\n");
scanf("%d",&size);
printf("enter the profit of assocaited length\n");
for(i=1;i<=size;i++)
{
printf("enter profit assocaited with length %d \n ",i);
scanf("%d",&p[i]);
}
printf("\n***************OUTPUT*****************\n");
result=recrsv_top_down(size);
printf("Maximum profit is %d\n",result);
return 0;
}
Sorry for the long post , but i have no option!!!
Please help me out !
