[알고리즘] 0-1 배낭 문제

개요

0-1 배낭 문제는 n개의 물건에 대해 최대 가치가 되도록 담는 알고리즘이다.

 

시간복잡도 분석

각각의 물건은 넣는다 / 넣지 않는다의 2개의 경우가 있으므로 단순히 시간 복잡도를 계산하면 O(2^n)이다.

Dynamic Programming으로 해결

i > 0이고 w > 0일 때, 전체 무게가 w를 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고 이익을 P[i][W]라고 하면 P[i][W]는 다음과 같이 구할 수 있다.

이 알고리즘의 시간복잡도는

이다.

 

W = 10이고, 품목이 다음과 같을 때의 0-1 배낭 문제 예시

 

문제점

불필요한 항을 계산한다. (위 그림에서 P[3][8]과 P[3][9]를 구할 필요는 없다.)

위 그림의 경우 총 n(4) * W(10)의 40번의 비교가 필요하다.

아래와 같이 필요한 항만 계산한다면 7번의 비교만 하면 된다.

개선된 알고리즘의 시간 복잡도는 

이다.