ナップサックアルゴリズムの最適解に含まれる特定の項目を取得するにはどうすればよいですか?

ナップサック アルゴリズムからの要素の取得

ナップサック アルゴリズムは、制約のある項目のセットから達成可能な最適な値を効率的に決定します。ただし、どの項目がそれに寄与するのかは指定されず、合計値のみが提供されます。

最適解に含まれる特定の要素を取得するには、アルゴリズム内で次の手順に従います。

for (size_t j = 1; j <= n; j++)
{
    for ( int w = 1; w <= W; w++)
    {
        ...
        if (dp[w][j] != dp[w][j-1] && dp[w][j] == dp[w - items[j-1].getWeight()][j-1] + items[j-1].getWeight())
        {
            // Mark element 'j' as included in the solution
        }
    }
}

これステップでは、現在の値と以前の値を比較し、項目がいつソリューションに追加されたかを識別します。選択された要素により、連続する値の差がその重みに等しくなります。

または、アルゴリズムの実行後、行列を逆に走査して、選択された項目を決定することもできます:

int line = W;
int i = n;
while (i > 0):
    if (dp[line][i] - dp[line - weight(i)][i-1] == item[i].getValue()):
        // Item 'i' is in the solution
        i--;
        line -= weight(i);
    else:
        i--;

このアプローチは、最適な解決策に寄与する要素を効率的に取得し、問題の解決策についてより包括的な洞察を提供します。

以上がナップサックアルゴリズムの最適解に含まれる特定の項目を取得するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。