0 - 1 KnapSack

개요

n개의 물건과 각 물건의 무게 w, 가치 v가 주어지고, 배낭의 용량 k가 주어질때 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 0 - 1 KnapSack의 경우 각 물건은 한개씩만 존재한다.

아이디어

위 문제는 Dynamic Programming을 활용해서 해결할 수 있다. DP 문제를 풀기위해 다음과 같이 점화식을 세울 수 있다.

DP[i][w] : 물건을 1 번째 물건 ~ i 번째 물건까지 고려하고 배낭의 용량이 w일때 최대 가치

 

위의 점화식에 따라 우리가 구하려는 답은 1 ~ n까지 즉, 모든 물건을 고려하고 배낭의 용량이 k일때 최대가치이므로  최적해는 DP[n][k]가 된다.

 

풀이

다음과같이 물건들의 무게와 가치, 가방의 무게가 주어진다고 가정하자

1. 가방의 무게가 0이거나 아무런 물건이 선택되지 않는 경우 배낭에 물건을 넣을 수 없으므로 최대값을 모두 0으로 초기화 시켜준다.

 

2. 만약 i번째 물건을 배낭에 담을수 있다면 ( i번째 물건의 무게가 배낭의 용량 w 보다 큰경우) 다음 로직에 따라 물건을 넣을지 말지 정한다.

case 1 : i 번째 물건을 넣지 않는 경우 : DP[i - 1][w] (i번째 물건을 넣지 않으므로 i - 1번째 까지 물건만 고려하면됨)

 

case 2 : i 번째 물건을 넣는 경우 : DP[i-1][w - w[i]] + v[i] ( i번째 물건을 넣을 공간을 만들기위해 w - w[i] 를 하고 i번째 물건의 가치 v[i]를 더해줌)

 

=> case1과 case2중 값이 더 큰값을 선택 DP[i][w] = max(DP[i-1][w][, DP[i-1][w - w[i]] + v[i])

 

DP[1][5]

= max(DP[i-1][w], DP[i-1][w-w[i]] + v[i])

= max(DP[0][5], DP[0][0] + 10)

= 10

 

 3. 

DP[2][4] = max(DP[1][4], DP[1][0] + 40) = max(0, 0 + 40) = 40

DP[2][5] = max(DP[1][5], DP[1][1] + 40) = max(10, 0 + 40) = 40

DP[2][9] = max(DP[1][9], DP[1][5] + 40) = max(10, 10 + 40) = 50

 

... 반복

 

최종값 = 90