동적 프로그래밍 알고리즘을 사용하여 PHP에서 배낭 문제를 해결하고 최적의 솔루션을 얻는 방법은 무엇입니까?

동적 프로그래밍 알고리즘을 사용하여 PHP의 배낭 문제를 해결하고 최적의 솔루션을 얻는 방법은 무엇입니까?

배낭 문제는 컴퓨터 과학의 고전적인 조합 최적화 문제 중 하나입니다. 배낭의 용량과 품목 세트가 주어지면 배낭에 넣을 품목을 선택하여 배낭에 있는 품목의 총 가치를 최대화하는 방법이 해결해야 할 배낭 문제의 핵심입니다.

동적 프로그래밍은 배낭 문제를 해결하는 일반적인 방법 중 하나입니다. 문제를 하위 문제로 분할하고 하위 문제에 대한 솔루션을 저장하여 최종적으로 최적의 솔루션을 얻습니다. 아래에서는 PHP에서 배낭 문제를 해결하기 위해 동적 프로그래밍 알고리즘을 사용하는 방법을 자세히 설명합니다.

먼저 배낭 문제의 입력과 출력을 정의해야 합니다.

입력:

• 항목 $weights, $weights[$i]의 무게 배열은 $i번째 항목의 무게를 나타냅니다
• $values ​​항목의 값 배열, $values[$i]는 $i번째 항목의 값을 나타냅니다.
• 백팩의 용량 $capacity는 백팩의 최대 용량을 나타냅니다.

출력:

• The 배낭에 있는 항목의 최대 총 가치

다음으로 하위 문제에 대한 솔루션을 저장하려면 2차원 배열 $dp를 정의해야 합니다. $dp[$i][$j]는 배낭 용량이 $j일 때 첫 번째 $i 항목의 최대 총 가치를 나타냅니다.

알고리즘의 흐름은 다음과 같습니다.

1. $dp 배열을 초기화하고 모든 요소를 ​​0으로 설정합니다.

2. 외부 루프는 $i = 1에서 $i = count($weights) - 1까지 항목의 인덱스를 순회합니다.

   • 내부 루프는 $j = 0에서 $j = 0부터 $i = count($weights) - 1까지 배낭의 용량을 순회합니다. $j = $ 용량:

     • 현재 항목의 무게 $weights[$i]가 배낭 $j의 용량보다 큰 경우 $dp[$i][$j] = $dp[$i - 1][$j] 즉, 현재 아이템은 배낭에 넣을 수 없으며, 최대 총 가치는 처음 $i - 1 아이템과 동일합니다.
     • 그렇지 않으면 현재 항목을 배낭에 넣을 수 있으며, 생성된 값은 $values[$i]에 항목을 넣기 전의 최대 총 값 $dp[$i - 1][$j - $weights[$ i ]], 현재 값과 비교하여 더 큰 값을 $dp[$i][$j]로 취합니다.
3. 백팩 용량이 $capacity일 때 첫 번째 개수($weights) 항목의 최대 총 값인 $dp[count($weights) - 1][$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 중국어 웹사이트의 기타 관련 기사를 참조하세요!