1

次の問題を解決しようとしていました。

加重和問題

私が以前に行った最も近い問題は Kadane のアルゴリズムであるため、「ここで終わる最大」アプローチを試みた結果、次の DP ベースのプログラムが作成されました。アイデアは、問題をより小さな同一の問題 (通常の DP) に分割することです。

#include<stdio.h>
#include<stdlib.h>


main(){
int i, n, m, C[20002], max, y, x, best, l, j;
int a[20002], b[20002];
scanf("%d %d", &n, &m);
for(i=0;i<n;i++){
    scanf("%d",&C[i]);
}
a[0] = C[0];
max = C[0];
for(i=1;i<n;i++){
    max = (C[i]>max) ? C[i] : max;
    a[i] = max;
}

for(l=0;l<n;l++){
    b[l] = 0;
}

for(y=2;y<m+1;y++){

    for(x=y-1;x<n;x++){

        best = max = 0;
        for(j=0;j<y;j++){
        max += (j+1) * C[j];
        }

        for(i=y-1;i<x+1;i++){
            best = a[i-1] + y * C[i];
            max = (best>max) ? best : max;
        }
        b[x] = max;
    }

    for(l=0;l<n;l++){
    a[l] = b[l];                 
    }
}
printf("%d\n",b[n-1]);
system("PAUSE");
return 0;
}

しかし、このプログラムは指定された制限時間内に動作しません (スペース制限は問題ありません)。この問題で使用するアルゴリズムのヒントを教えてください。

編集。

コードの説明は次のとおりです: Kadane の場合と同様に、私のアイデアは、特定の C[i] を調べ、次に C[i] で終わる m サブシーケンスの最大加重合計を取り、最後にすべての最大値を取ることです。すべての i にわたるそのような値。これで答えが得られます。ここで、C[i] で終わる m サブシーケンスを見て、最大加重合計を取る場合、これは C[0] に含まれる (m-1) サブシーケンスの最大加重合計を取るのと同じであることに注意してください。 C[i-1]に。そして、これは元の問題と同じ小さな問題です。そこで、再帰を使用します。関数の二重呼び出しを避けるために、値 f[i][j] のテーブルを作成します。ここで、f[ii][j] は、n を i に置き換え、m を に置き換えた問題と同じ問題の答えです。 j. つまり、f[i][j] のテーブルを作成し、最終的な答えは f[n-1][m] です (つまり、メモ化を使用します)。ここで、エントリ f[i][j] を計算するには前の列のみが必要であることに注意してください。配列のみを保持するだけで十分です。これらの配列は「a」と「b」です。

長くなってすみません、仕方ありません。:(

4

2 に答える 2

0

0/1 Knapsack without repetition各ステップでアイテムを含めるかどうかを決定するアプローチを試してください。

とから変化する部分問題の を表し、MWS(i, j)目標は の値を見つけることです。optimal maximum weighted sumC[i...N]i0 <= i <= N1 <= j <= MMWS(0, 1)

MWS(i, j) は次のように再帰的に表すことができます。

ここに画像の説明を入力

境界条件の扱いは演習として残しておきます。

于 2012-06-02T17:43:17.290 に答える
0

あなたの一般的なアプローチは正しいです。しかし、アルゴリズムに問題があります。

内側のループの本体を置き換えることができます

    best = max = 0;
    for(j=0;j<y;j++){
    max += (j+1) * C[j];
    }

    for(i=y-1;i<x+1;i++){
        best = a[i-1] + y * C[i];
        max = (best>max) ? best : max;
    }
    b[x] = max;

と

   b[x] = MAX(b[x-1],a[x-1] + y * C[x]);

これにより、アルゴリズムの時間の複雑さが改善されます。b[i]つまり、すべての再計算を避けますi < x。動的計画法の一般的な特性。

于 2012-06-02T17:09:20.217 に答える