01배낭 문제의 동적 프로그래밍

동적 프로그래밍의 기본 아이디어:

동적 프로그래밍 알고리즘은 일반적으로 최적의 하위 구조 속성이라고 부르는 특정 최적 속성의 문제를 해결하는 데 사용됩니다.

동적 프로그래밍 알고리즘은 분할 정복 방법과 유사합니다. 기본 아이디어는 해결해야 할 문제를 여러 하위 문제로 분해하고 하위 문제를 먼저 해결한 다음 원래 문제에 대한 해결책을 얻는 것입니다. 이러한 하위 문제의 솔루션에서. 분할 정복 방식과의 가장 큰 차이점은 동적 계획법으로 해결하기에 적합한 문제의 경우 분해 후 얻은 하위 문제가 서로 독립적이지 않은 경우, 즉 다음 하위 단계의 솔루션이 되는 경우가 많다는 것입니다. 이전 하위 단계의 솔루션을 기반으로 합니다.

이 유형의 문제를 해결하기 위해 분할 정복 방법을 사용하면 분해로 얻은 하위 문제의 수가 너무 많아지고 일부 하위 문제는 여러 번 다시 계산됩니다. 해결된 하위 문제에 대한 답을 저장하고 필요할 때 답을 찾을 수 있다면 많은 반복 계산을 피하고 시간을 절약할 수 있습니다. 해결된 모든 하위 문제에 대한 답을 기록하기 위해 표를 사용할 수 있습니다. 하위 문제가 나중에 사용되는지 여부에 관계없이 계산된 한 해당 결과는 테이블에 채워집니다.

문제 설명:

N개의 아이템과 배낭이 주어졌습니다. 항목 i의 무게는 Wi, 값은 Vi, 배낭의 용량은 C입니다. 배낭으로 옮겨지는 아이템의 총 가치를 극대화하려면 배낭에 넣을 아이템을 어떻게 선택해야 하나요? ?

항목을 선택할 때 각 항목에 대해 배낭에 넣거나 배낭에 넣지 않는 두 가지 옵션만 있습니다. 항목 i를 여러 번 로드할 수 없으며 항목의 일부만 로드할 수도 없습니다. 따라서 이 문제를 0-1 배낭 문제라고 합니다.

문제 분석: V(i,j)는 용량이 j(1

(1)   V(i,0)=V(0,j)=0 

(2)   (a)  V(i,j)=V(i-1,j)    j<wi  

      (b)  V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) }   j>wi

(1) 공식은 다음과 같습니다. i번째 항목의 무게가 배낭의 용량보다 크면 i-의 최대값은 - 아이템 1개당 얻을 수 있는 최대 가격은 동일합니다. 즉, i 아이템은 배낭에 넣을 수 없습니다.

수식 (2)는 i번째 항목의 무게가 배낭의 용량보다 작은 경우 두 가지 상황이 발생합니다. (a) i번째 항목이 배낭에 적재되지 않은 경우 값은 다음과 같습니다. i-1개의 아이템을 용량 j의 배낭에 넣어서 얻은 값. (b) i번째 아이템을 배낭에 넣으면, 배낭 아이템의 가치는 용량 j-wi인 배낭에 있는 i-1번째 아이템의 가치에 i번째 아이템의 가치 vi를 더한 값과 같습니다. ; 당연히, 가장 큰 가치를 지닌 것이 j 용량의 배낭에 첫 번째 i개 항목을 적재하기 위한 최적의 솔루션입니다.

추천 튜토리얼: PHP 튜토리얼

위 내용은 01배낭 문제의 동적 프로그래밍의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!