動的計画法アルゴリズムを使用してPHPのナップザック問題を解決し、最適な解決策を得るにはどうすればよいですか?

動的計画法アルゴリズムを使用して PHP のナップザック問題を解決し、最適な解を得るにはどうすればよいでしょうか?

ナップザック問題は、コンピューター サイエンスにおける古典的な組み合わせ最適化問題の 1 つです。アイテムのセットとナップザックの容量が与えられた場合、ナップザック内のアイテムの合計価値を最大化するためにナップザックに入れるアイテムをどのように選択するかが、解決すべきナップザック問題の核心です。

動的プログラミングは、ナップザック問題を解決する一般的な方法の 1 つです。問題をサブ問題に分割し、そのサブ問題に対する解を保存することにより、最終的に最適な解が得られます。以下では、動的計画法アルゴリズムを使用して PHP のナップザック問題を解決する方法を詳しく説明します。

最初に、ナップザック問題の入力と出力を定義する必要があります:

入力:

• アイテムの重み配列 $weights $weights[ $i] は、$i 個のアイテムの重量を表します。
• アイテムの値配列$values、$values[$i] は、$i 個のアイテムの値を表します。
• バックパックの容量$容量、バックパックの最大容量を示します

出力:

• バックパック内のアイテムの最大合計値

次に、部分問題の解を保存するために使用する 2 次元配列 $dp を定義する必要があります。 $dp[$i][$j]はバックパックの容量が$jのときの最初の$i個のアイテムの合計の最大値を表します。

アルゴリズム フローは次のとおりです。

1. $dp 配列を初期化し、すべての要素を 0 に設定します。

2. 外側のループは、項目のインデックスを $i = 1 から $i = count($weights) - 1 まで走査します。

   • 内側のループループはバックパックの容量を $j = 0 から $j = $capacity まで調べます:

     • 現在のアイテムの重量 $weights[$i] がバックパックの容量より大きい場合$j の場合、$dp[$i] [$j] = $dp[$i - 1][$j]、つまり、現在のアイテムはバックパックに入れることができず、最大合計値は次と同じになります。前の $i - 1 項目。
     • それ以外の場合は、現在のアイテムをバックパックに入れることができ、それによって生成される値 $values[$i] にアイテムを入れる前の最大合計値 $dp[$i - 1][$ j - $weights[$i]] を現在の値と比較して、大きい方の値を $dp[$i][$j] として採用します。
3. $dp[count($weights) - 1][$capacity] を返します。つまり、バックパック内の最初の count($weights) 個のアイテムには次の値が含まれます。 $capacity の容量はその時点での最大合計値です。

以下は、PHP コードを使用したナップザック問題の動的プログラミング アルゴリズムです。

function knapsack($weights, $values, $capacity) {
    $dp = [];
    for ($i = 0; $i < count($weights); $i++) {
        $dp[$i] = [];
        for ($j = 0; $j <= $capacity; $j++) {
            $dp[$i][$j] = 0;
        }
    }
    
    for ($i = 1; $i < count($weights); $i++) {
        for ($j = 0; $j <= $capacity; $j++) {
            if ($weights[$i] > $j) {
                $dp[$i][$j] = $dp[$i - 1][$j];
            } else {
                $dp[$i][$j] = max($dp[$i - 1][$j], $values[$i] + $dp[$i - 1][$j - $weights[$i]]);
            }
        }
    }
    
    return $dp[count($weights) - 1][$capacity];
}

上記のコードを使用すると、knapsack($weights, $values, $capacity ) 関数を使用してナップザック問題を解決し、最適解を取得します。

この記事が、動的計画法アルゴリズムを使用して PHP のナップザック問題を解決し、最適な解を得る方法を理解するのに役立つことを願っています。

以上が動的計画法アルゴリズムを使用してPHPのナップザック問題を解決し、最適な解決策を得るにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。