algorithm - 隣接する要素が k 個を超えないように、配列内の n 個の要素の最大合計を見つける

Question

これとほぼ同じ: 隣接する要素が k 個を超えないように、配列内の要素の最大和を見つける

ただし、選択できる要素は n 個に制限されています。DPアルゴリズムを変更してこれを機能させるにはどうすればよいですか?

Answer 1

うーん、もっとはっきりさせてください。

質問: 隣接する要素が K 個を超えないように、配列内の n 個の要素の最大合計を見つけます

let int f[i][j][k]は、最初の i 要素の最大合計を意味し、合計 j 個の要素を使用し、最後の k 個の要素が使用されます。let bool g[i][j][k]は、特定の組み合わせを取得できるかどうかを示します。例えば。g[1][1][2] は偽です。これは重要です。制限がないと、f は不可能な答えを生成する可能性があるからです。

最初に、memset f と g をすべてゼロに設定し、g[0][0][0] を true に設定します。この DP 問題を解決するには、前方再帰を使用できます。明らかに、数字に遭遇するたびに、それを選択するか、放棄するかの 2 つの選択肢があります。これにより、再帰式が得られます。

f[i][j][k] can infer f[i+1][j+1][k+1], or
f[i][j][k] can infer f[i+1][j][0]

したがって、擬似コードは次のようになります。

memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
g[0][0][0]=true;
for (int i=0;i<array.size();i++)
    for (int j=0;j<=n;j++)
        for (int k=0;k<=K;k++) if (g[i][j][k]) {
            f[i+1][j][0]=max(f[i+1][j][0],f[i][j][k]);
            f[i+1][j+1][k+1]=max(f[i+1][j+1][k+1],f[i][j][k]+array[i]);
            g[i+1][j][0]=true;
            g[i+1][j+1][k+1]=true;
        }

最終結果は次のようになります。

ans=0;
for (i=0;i<=K;i++)
    ans=max(ans,f[array.size()][n][i]);
return ans;

上記は正確に j 要素を与えます。最大で j 要素を取得したい場合は、次のように変更できます。

ans=0;
for (i=0;i<=n;i++)
    for (j=0;j<=K;j++)
        ans=max(ans,f[array.size()][i][j]);
return ans;