PHP의 0-1 배낭 문제에 대한 효율적인 솔루션을 얻기 위해 역추적을 사용하는 방법은 무엇입니까?

PHP에서 0-1 배낭 문제에 대한 효율적인 솔루션을 얻기 위해 역추적을 사용하는 방법은 무엇입니까?

배낭 문제는 많은 알고리즘 강좌와 인터뷰에서 자주 언급되는 고전적인 조합 최적화 문제입니다. 일반적인 배낭 문제 중 하나는 0-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는 현재 최대값, 현재 선택한 항목의 총 무게와 총 값, 현재 선택한 항목 인덱스, 배낭의 총 무게, 항목의 무게와 값 배열을 포함한 일련의 매개변수를 받습니다. 함수 본문에서는 먼저 모든 항목이 선택되었는지, 아니면 배낭이 채워졌는지 확인합니다. 그렇다면 현재 선택한 항목의 전체 값이 반환됩니다. 그런 다음 현재 항목을 선택하거나 선택하지 않고 두 경우 모두에서 최대값을 재귀적으로 해결하고 둘 중 더 큰 값을 반환합니다. 마지막으로 최대 출력 값이 문제에 대한 해결책입니다.

이 알고리즘의 시간 복잡도는 기하급수적으로 증가하므로 대규모 문제를 처리할 때 특정 성능 문제가 발생합니다. 그러나 실제 적용에서는 계산된 결과를 저장하여 반복 계산을 방지하고 프로그램 효율성을 향상시키는 암기 기술을 추가할 수 있습니다.

위 내용은 PHP의 0-1 배낭 문제에 대한 효율적인 솔루션을 얻기 위해 역추적을 사용하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!