Rod Cutting without using dynamic approach

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 !