1

長さnインチのロッドと、i = 1、2、... nの価格piの表が与えられた場合、ロッドを切断して部品を販売することで得られる最大収益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 または long long の使用に固執する必要があります。

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

2つのことがあります。1 つは を返します。r[n]これは である必要がありますr[n-1]。第 2 に、 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 に答える