Cutting a Rod for the Best Price

Problem : Given a rod of n units and the price for each lenght of the unit, what is the optimal way to cut the rod so that the price is maximum.

For ex:

i   :      1    2    3    4     5      6      7       8
=============================================================
V :        2    4    6    9    10      15    17      25


If we cut the rod with 1 unit length each of 8 units, then the price is 8.
If we cut the rod with 2 unit length each of 4 units , then the price is 20
If we cut the rod with two 1 units and three 2 unit length, then price is 17

Now, to cut 8 unit rod, we need to find out what is teh best value for B[8-i] + V(i), i<=8

So the solution is :

S[i] = Max { V(j) + S[i-j], for 0<=j<=i

S[1] = Max { S[0] + v(1)} = 0 + 2 = 2
S[2] = Max { S[0] + v(2), S[1] +v(1)} { 0 + 4, 2 + 2} = 4
S[3] = Max { S[0] + v(3) , S[1] + v(2) , S[2] + v(1)} = { 6, 2+4, 4+2 } = 6
S[4] = Max { S[0] + v(4), S[1] + V(3), S[2] + v(2) , S[3] + v(1) = { 9,2+6,4+4,6+2} = 9
...
...
S[8]= 19  For 1,7 combination (2 + 17 ) = 19

C++ Program to Solve the above problem using dynamic programming:
void CutRod(int B[],int n)
{
    int S[9];

    for(int i=0;i<=n;i++)
        S[i]=INT_MIN;

    S[0]=0;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {                     //S[0]=0, S[1]=1
            if(S[i]<S[i-j]+B[j-1])   //S[2] <S[1]+B[1] or S[2] < S[0] +B[2]
            {
                S[i]=S[i-j]+B[j-1];
            }

        }
    }

int max=0;
for(int i=1;i<=n;i++)
if(S[i]>max)
max=S[i];

cout<<" Best price is :"<<max<<endl;

}

Output is : 19