3

私はこの問題を抱えています.正の数の配列が与えられた場合、隣接する2つの要素が選択されないように、要素の最大合計を見つける必要があります. 最大値は特定の特定の K よりも小さくなければなりません。 k なしで同様の問題の行を考えてみましたが、これまでのところ失敗しました。後者の問題については、次の dp っぽいソリューションがあります。

    int sum1,sum2 = 0;
    int sum = sum1 = a[0];

    for(int i=1; i<n; i++)
    {
        sum = max(sum2 + a[i], sum1);
        sum2 = sum1;
        sum1 = sum;
    }

誰かが私の現在の問題を進める方法についてのヒントを教えてもらえますか??

4

4 に答える 4

4

頭のてっぺんから考えられる最高のものは、O(n*K) dp です。

int sums[n][K+1] = {{0}};
int i, j;
for(j = a[0]; j <= K; ++j) {
    sums[0][j] = a[0];
}
if (a[1] > a[0]) {
    for(j = a[0]; j < a[1]; ++j) {
        sums[1][j] = a[0];
    }
    for(j = a[1]; j <= K; ++j) {
        sums[1][j] = a[1];
    }
} else {
    for(j = a[1]; j < a[0]; ++j) {
        sums[1][j] = a[1];
    }
    for(j = a[0]; j <= K; ++j) {
        sums[1][j] = a[0];
    }
}
for(i = 2; i < n; ++i) {
    for(j = 0; j <= K && j < a[i]; ++j) {
        sums[i][j] = max(sums[i-1][j],sums[i-2][j]);
    }
    for(j = a[i]; j <= K; ++j) {
        sums[i][j] = max(sums[i-1][j],a[i] + sums[i-2][j-a[i]]);
    }
}

sums[i][j]a[0..i]を超えない隣接しない要素の最大合計を含みますj。解決策はsums[n-1][K]最後にあります。

于 2012-04-21T18:35:00.823 に答える
0
  1. 元のアレイ（A1）のコピー（A2）を作成します。
  2. 配列（A2）で最大値を見つけます。
  3. 前のネイバーの前のすべての値と次のネイバーの後の値を新しい配列に抽出します（A3）。
  4. 新しい配列（A3）で最大値を見つけます。
  5. 合計がkよりも大きいかどうかを確認します。合計がチェックに合格すると、完了です。
  6. そうでない場合は、コピーした配列（A2）に戻り、2番目の大きい値（手順3で見つかりました）を削除して、手順3からやり直す必要があります。
  7. 最大数で使用できる数の組み合わせがなくなったら（つまり、ステップ1で見つかった数+配列内の他の数がkより大きい）、元の配列（A1）からそれを削除し、ステップ0からやり直します。
  8. 何らかの理由で有効な組み合わせがない場合（たとえば、配列が3つの数値のみであるか、数値の組み合わせがk未満でない場合）、例外をスローするか、より適切と思われる場合はnullを返します。
于 2012-04-21T18:19:02.540 に答える
0

最初のステップとして設定した「k」制約のない問題の解決策を次に示します。

上記の解決策は、次の for ループの if 条件を制約を含めるように修正するだけで、k 制約を持つように簡単に拡張できます。

// Subproblem solutions, DP
for (int i = start; i <= end; i++) {
    int possibleMaxSub1 = maxSum(a, i + 2, end);
    int possibleMaxSub2 = maxSum(a, start, i - 2);

    int possibleMax = possibleMaxSub1 + possibleMaxSub2 + a[i];
    /*
    if (possibleMax > maxSum) {
        maxSum = possibleMax;
    }
    */
    if (possibleMax > maxSum && possibleMax < k) {
        maxSum = possibleMax;
    }
}

元のリンクに投稿されているように、このアプローチは記憶を追加することで改善できるため、サブ問題の繰り返しに対する解が再計算されません。または、ボトムアップの動的計画法のアプローチを使用して改善できます (現在のアプローチは再帰的なトップダウンのアプローチです)。

ここでボトムアップアプローチを参照できます: https://stackoverflow.com/a/4487594/1110808

于 2012-10-23T01:09:37.617 に答える
0

最初のアイデア: ブルート フォース

インデックスのすべての正当な組み合わせを反復し、その場で合計を構築します。

K を超えたら 1 つのシーケンスで停止します。

より大きなものを見つけるまでシーケンスを保持します。それはまだ K よりも小さいです

2番目のアイデア：これを強制的に分割して征服することができるかもしれません...

于 2012-04-21T18:44:46.157 に答える