부분 집합의 합을 이해하는 자원 할당

Question

를 해결하기 위해 나는 인터넷에이 코드를 발견하고 내가 힘든 시간을 이해하는 데. 아무도 약간의 설명을 주면 도움이 될 것입니다.

SubsetSum(n, W): 
Initialize M[0,w] = 0 for each w = 0,...,W 
Initialize M[i,0] = 0 for each i = 1,...,n 
For i = 1,...,n: for every row 
For w = 0,...,W: for every column 
If w[i] > w: case where item can’t fit 
    M[i,w] = M[i-1,w] 

M[i,w] = max(which is best? 
M[i-1,w], 
w[j] + M[i-1, W-w[j]] 
) 
Return M[n,W] 

Answer 1

분류

이 Dynamic Programming의 전형적인 애플리케이션이다.

변수

하자 w[i]는 항목 i, W 글로벌 용량의 무게와 M[i,w] 첫 i 객체를 사용하여 부분 집합 합 문제의 최적의 솔루션과 남은 용량 w을 나타낸다.

주요 관찰

이전 값 M[i-1,*]에서 최적의 솔루션 M[i,w]를 얻으려면, 우리는 다음 항목 i을 포함하거나 생략 할 수 있습니다. 우리가 항목 i 다음 M[i,w] = w[i] + M[i-1, w-w[i]]을 포함하는 경우 (i 항목의 포함에 대한 중량 w[i] 첨가하지만 동일한 양만큼 잔존 용량을 감소시키는 단계;를 포함 j 슬라이드에 오타가있다). 우리가 항목 i을두고 있는지, 다음 M[i,w] = M[i-1,w] (이전 솔루션에 대한 값을 추가하고 같은 남은 용량을 유지하지 않음).

우리는 따라서 우리는이 두 값의 최대 값을 가지고, 최적 (최대) 솔루션에 관심이 있습니다. 어쨌든 우리는 M[i,*]의 지수를 줄였습니다. 그것은 우리가 값 M[i',*]을 알고있는 경우에, 우리는 i > i'에 대한 값을 M[i,*]을 계산할 수 있습니다 의미한다. 이것이 바로 아이디어를 차 프로그래밍 동적이다.

참고

첫번째 라인 초기화하고 값이 w[i]w 잔존 용량보다 큰 경우에, 우리는 분명 i 항목을 포함 할 수 없다. 반환 값 M[n,W]은 전체 용량으로 시작하는 모든 항목을 포함하는 최적의 솔루션을 설명합니다.