Dynamic Programing : Rod cutting implementation error

1
votes

Given a rod of length n inches and a table of prices pi for i = 1, 2,... n, determine the maximum revenue rn obtainable by cutting up the rod and selling the pieces.

Bottom_Up_Cut_Rod(p, n)
1 let r[0...n] be a new array
2 r[0] = 0
3 for j = 1 to n
4 q = -infinity
5 for i = 1 to j
6 q = max(q; p[i] + r[j - i])
7 r[j] = q
8 return r[n]

Implementation

#include <iostream>
#include <algorithm>

using namespace std;

int RodCut(long long P[],long long n)
{
    long long r[n];
    r[0]=0;
    for(long long j=0;j<n;j++)
    {
         long long q = -100000;
         for(long long i=0;i<j;i++)
         {
             q = max(q , P[i] + r[j-i]);
         }
         r[j] = q;
    }

    return r[n];
}

int main()
{
    long long num;
    long long N;
    long long K;

    cin>>N;

    long long a[N];
    for (long long i = 0; i < N; i++)
    {
        cin>>num;
        a[i] = num;
    }

    int res = 0;
    res = RodCut(a,N);

    cout<<"Answer : "<<res;

    return 0;
}

My input is 1 5 8 9 10 17 17 20 24 30, but output is 2686348. What is wrong with my code?

2
c++algorithmdynamic-programming
Have you tried debugging, may be that would be helpful – Forever Learner
Actually, your array r is an array of length n. When you write return r[n]; you actually requests to return an element which is not in your array. You better try return r[n-1]; – Morwenn
Want to give your actual input? (hint: what is N?) – Sam DeHaan
@SamDeHaan: N is 10, in the given case. – Justin ᚅᚔᚈᚄᚒᚔ
for return r[n-1] I got output 4692046. – user1370786

2 Answers

1
votes

There are several issues. You want the main loop to go from j = 1 to n, because it represents the best you can do using j elements.

You should stick to using either ints or long longs.

int r[n+1];
r[0]=0;

// Calculate best we can do with j elements
for(int j=1;j<=n;j++) {
    int q = -100000;
    for(int i=0;i<j;i++) {
        q = max(q , P[i] + r[j-i-1]);
    }
    r[j] = q;
}

return r[n];

This seems to give me the right solution for a variety of inputs.

0
votes

There are two things. One is returning r[n], which should be r[n-1]. Second, start j from 1 to n, since r[0] is getting replaced with -100000 in the first round.

Also, r[0] should be P[0]; i.e. you'll atleast make P[0] money given a rod with length 1.

Also, note that q should be P[j], thats the minimum you'll make. 

So assuming the array is P[0..n] // not including n
and r[0..n] is your memo for applying DP

foreach index from (0..n] // not including n
    r[index] = P[index]
    foreach splitIndex from (0..index] // not including index
        r[index] = max(r[index], P[splitIndex] + r[index-splitIndex-1]
return r[n-1]