# 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!!!

In recrsv_top_down, declare result = -1000 as a local variable.
• @laura Well, your problem was the fact that the global result got tampered by recursive calls. Actually, in professional software development, usage of globals is most likely an indication of a design error. Jun 17 '17 at 18:21