1

给定一根长度为 n 英寸的棒和一个价格表 pi，i = 1, 2,... n，确定通过切割棒并出售碎片可获得的最大收益 rn。

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]

执行

#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;
}

我的输入是1 5 8 9 10 17 17 20 24 30，但输出是2686348。我的代码有什么问题？

4

2 回答 2

1

有几个问题。您希望主循环从 j = 1 变为 n，因为它代表了使用 j 元素可以做的最好的事情。

您应该坚持使用整数或长整数。

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];

这似乎为我提供了适用于各种输入的正确解决方案。

于 2012-05-02T19:11:25.300 回答
0

有两件事。一是回归r[n]，应该是r[n-1]。其次， start j from 1 to n，因为在第一轮中r[0]被替换为。-100000

此外，r[0]应该是P[0]；P[0]即，给定长度为 1 的杆，您至少会赚钱。

另外，请注意q应该是P[j]，那是您将要做的最低限度。

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]
于 2012-05-02T19:03:53.427 回答