1
$\begingroup$

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 !

$\endgroup$
1
$\begingroup$

In recrsv_top_down, declare result = -1000 as a local variable.

$\endgroup$
  • $\begingroup$ it worked ! thanks a lot !!!!!!!can you please explain the logic !!! $\endgroup$ – laura Jun 17 '17 at 16:17
  • $\begingroup$ @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. $\endgroup$ – coderodde Jun 17 '17 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.