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 !