PHP でバックトラッキングを使用して 0-1 ナップザック問題を効率的に解決するにはどうすればよいですか?

バックトラッキングを使用して、PHP で 0-1 ナップザック問題を効率的に解決するにはどうすればよいですか?

ナップザック問題は、多くのアルゴリズム コースやインタビューでよく言及される古典的な組み合わせ最適化問題です。一般的なナップサック問題の 1 つは 0-1 ナップサック問題で、これは最も基本的なナップサック問題の 1 つでもあります。 0-1 ナップザック問題は次のように説明されます。項目のセットが与えられると、各項目には重みと値があります。ここで、容量 C のバックパックがあります。アイテムの総重量がバックパックの容量を超えず、アイテムの合計価値が最大になるように、バックパックに入れるいくつかのアイテムを選択する必要があります。

バックトラッキング法は、組み合わせ最適化問題を解くための古典的なアルゴリズムであり、可能な解空間を絶えず試して最終的に最適解を見つけます。バックトラッキング法は、0-1 ナップザック問題の効率的な解決策を達成する上で大きな役割を果たします。以下は、バックトラッキング手法を使用して PHP で 0-1 ナップサック問題を実装する具体的なコード例です。

<?php

// 通过回溯法解决0-1背包问题

/**
 * @param int $maxValue 当前最大价值
 * @param int $curWeight 当前已选择物品的总重量
 * @param int $curValue 当前已选择物品的总价值
 * @param int $curIndex 当前已选择的物品索引
 * @param int $totalWeight 背包的总重量
 * @param int[] $weights 物品的重量数组
 * @param int[] $values 物品的价值数组
 * @return int 当前已选择物品的最大价值
 */
function knapsack($maxValue, $curWeight, $curValue, $curIndex, $totalWeight, $weights, $values)
{
    if ($curIndex == count($weights) || $curWeight == $totalWeight) {
        return $curValue;
    }
  
    $value1 = 0;
    if ($curWeight + $weights[$curIndex] <= $totalWeight) {
        // 选择当前物品
        $value1 = knapsack($maxValue, $curWeight + $weights[$curIndex], $curValue + $values[$curIndex], $curIndex + 1, $totalWeight, $weights, $values);
    }
  
    // 不选择当前物品
    $value2 = knapsack($maxValue, $curWeight, $curValue, $curIndex + 1, $totalWeight, $weights, $values);

    return max($value1, $value2);
}
  
$weights = [2, 3, 4, 5]; // 物品的重量数组
$values = [3, 4, 8, 9]; // 物品的价值数组
$totalWeight = 9;  // 背包的总重量

$maxValue = knapsack(0, 0, 0, 0, $totalWeight, $weights, $values);

echo "最大价值为：" . $maxValue;

?>

上記のコードは、再帰を使用して 0-1 ナップサック問題を解決します。関数 knapsack は、現在の最大値、現在選択されているアイテムの総重量と合計値、現在選択されているアイテムのインデックス、バックパックの総重量、および重量と値を含む一連のパラメーターを受け取ります。項目の配列。関数本体では、まずすべてのアイテムが選択されているか、バックパックがいっぱいになっているかを判断し、満たされている場合は、現在選択されているアイテムの合計値を返します。次に、現在の項目を選択するか、現在の項目を選択しないかを試行し、両方の場合の最大値を再帰的に解決し、2 つの値のうち大きい方の値を返します。最後に、最大出力値が問題の解決策です。

このアルゴリズムの時間計算量は指数関数的であるため、大規模な問題を扱う場合には特定のパフォーマンスの問題が発生します。ただし、実際のアプリケーションでは、計算結果を保存する記憶技術を追加して、計算の繰り返しを回避し、プログラムの効率を向上させることができます。

以上がPHP でバックトラッキングを使用して 0-1 ナップザック問題を効率的に解決するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。