Knapsack Algorithm 배낭 문제 정리

가정

최대 무게가 정해진 가방이 있다. 그리고 각기 다른 가치와 무게를 지닌 물건들이 있다.

 

이 물건들을 가방에 집어넣을 때, 가치가 최대가 되게끔 집어넣는 방법은 어떤 게 있을까?

 

 

 

방법

1. 가능한 모든 경우의 수를 다 세본다. (Brute-Force)

 

2. 가치가 가장 최대인 물건들만 우선적으로 집어 넣는다. 그리디 (Greedy)

 

3. DP(Dynamic Programming), 동적 계획법을 사용한다.

 

 

 

진행

 

3번을 살펴보도록 하고 다음과 같이 가정하자.

 

i == 물건들의 번호이자 넣는 것이 허용되는 범위 (i=4이면, 1, 2, 3, 4번의 물건만 고려한다는 뜻)

j == 견딜 수 있는 무게 (j=3이면, 가방 무게를 3으로 한정 짓는다는 뜻)

 

(처음 이렇게 보면 상당히 추상적인데, 2중 for문의 루프 변수들이라고 생각해두면 편하다.)

 

 

 

그리고 dp[][] 배열에는 당연히 i와 j에 대한 가치의 최댓값이 저장된다.

 

예를 들어 dp[2][3]는 i=2, j=3일 때의 가방에 넣을 수 있는 최댓값을 저장하고 있다. 

 

다시 한글로 풀어쓰면, 2번까지의 물건만 넣을 수 있고 가방의 무게를 3까지 한정지었을 때 가방에 넣은 최대 가치이다.

 

 

 

당연히 첫 디폴트 값은,

 

dp[i][0] = 0이다. (견딜 수 있는 무게가 0인데 i가 몇번째까지 허용 가능한지는 따질 필요 없다.)

 

그리고 당연히,

 

dp[0][j] = 0이다. (견딜 수 있는 무게가 아무리 커도 0번째까지만(존재하지 않음)의 물건만 넣는 것이 허용되니까)

 

 

 

더불어 W, V 배열도 아래와 같다고 하자.

 

W[] == 각각의 물건 무게 (0번은 없으니까 1번부터 시작)

V[] == 각각의 물건 가치 (0번은 없으니까 1번부터 시작)

 

 

 

먼저 일반화된 점화식을 보기 전에 가장 중요한 핵심을 살펴보자.

 

 

 

j가 7이면, 버틸 수 있는 무게가 7인 것이다.

 

그럼 여기서 i가 3, 즉 3번째인 물건의 무게는 당연히 W[3]이다.

 

지금 버틸 수 있는 최대치 7에 3번의 물건을 넣으면 '남는 무게'는 당연히 7 - W[3]이다.

 

그리고 3번의 가치는 V[3]이므로 3번을 가방에 넣을 때 우리는 V[3]만큼의 가치를 가지게 된다.

 

근데 여기서 7 - W[3]만큼의 무게가 남는다.

 

 

 

이 남은 무게에는 3번 "이전의" 물건들인 1번, 2번 물건들 중 당연히 무게가 허용하는 선에서  · · · ⓐ

 

보다 큰 가치의 물건 모두를 넣을 것이다.

 

(W[3]이 딱딱하면 W[3]을 5라고 가정해보자 그러면, 2만큼의 무게를 더 집어넣을 수 있는 공간이 남아있다.)

 

 

 

즉, 현재의 최댓값은 이렇게 구할 수 있다.

 

dp[i][j] = dp[i-1][7-W[3]] + V[3];   (수를 넣어보면 d[3][7] = dp[2][2] + V[3])

 

 

 

( ⓐ번에서 ) 흐름을 놓쳤다면,

 

위의 식에서 i-1이 어디서 나왔냐고 물을 수 있는데 먼저 i-1은 2가 된다. (i=3)

 

위의 값 2는 3번 이전의 물건들, 즉 1~2번의 물건들을 나타내고

 

dp에는 그 중 최대가 저장되어 있다(dp에는 해당 i번째까지의 물건들 중 최댓값만 저장하기로 했으니까)

 

 

 

여기서 일반화를 하기엔 이르다.

 

왜냐면 우린 아직 해당 3번 물건이 가방 무게 최대치인 j(=7)를 넘는지 안 넘는지를 고려하지 않았으니까.

 

만약 그대로 코드를 돌리게 되면 오류가 난다. 7-W[3]의 결과가 음수라고 생각해보라, 끔찍하다.

 

 

 

그럼 i번째 물건의 무게를 고려하여 점화식을 세워보자.

j < W[i] 일 때, dp[i][j] = dp[i-1][j]
j >= W[i] 일 때, dp[i][j] = max( dp[i-1][j] , dp[i-1][j-W[i]] + V[i] )

...가 된다.

 

 

 

위의 첫번째 조건( j < W[i] )에서 뜬금 없이 dp[i][j] = dp[i-1][j] 가 나와서 곤혹스러울 것이다. (knapsack을 모른다면)

 

왜 i번째 무게 W[i]가, 현재 가방이 버틸 수 있는 무게의 최대치인 j보다 클 때,

 

i의 이전 물건들 중 j에 넣을 수 있는 최대를 저장하게 되는지를 말이다.

 

 

 

사실 위의 말에 답이 있다.

 

현재 물건의 무게 W[i]가 최대치 j를 벗어나면 못 넣게 되고,

 

그래서 그 이전의 물건들(= i-1) 중 가치를 최대로 하는 물건들만 넣을 수 있게 된다.

 

그리고 두번째 조건을 보면, 당연히 해석이 한결 수월해진다. 아래와 같다.

j가 i번째 무게를 허용 가능하게 되면, ( j >= W[i] )
i 이전의 물건들 중 j에 넣을 수 있는 최대치 or
( 현재 i번째 물건 가치 V[i] + 남은 무게에 대한 최대치 dp[i-1][j-W[i]] )
...중에서 최대를 골라 저장하면 된다.

 

 

 

처음 이해가 잘 안 갈 때에는 표준으로 풀이된 예제를 뚫.어.지.게 살펴보면서 계속 생각해봐야 한다.

간단한 범위의 값을 넣어가며 공부하는 것도 도움이 많이 되는 것 같다.

 

 

 

j < W[i] 일 때, dp[i][j] = dp[i-1][j]
j >= W[i] 일 때, dp[i][j] = max( dp[i-1][j] , dp[i-1][j-W[i]] + V[i] )