배낭 문제(Knapsack Problem)

배낭 문제는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법입니다.

 

이 배낭 문제는 두 가지로 나누어집니다.

• 짐을 쪼갤 수 있는 경우인 분할 가능 배낭(Fractional Knapsack)
• 짐을 쪼갤 수 없는 경우인 0-1 배낭(0-1 Knapsack)

 

분할 가능 배낭

---

이 문제는 그리디 알고리즘을 적용하면 다항 시간 안에 풀 수 있습니다.

 

짐을 쪼갤 수 있는 경우에는 무게당 가치가 제일 높은 물건이 먼저 들어가야 하므로

각 물건의 가치/무게를 구한 다음 가장 높은 물건부터 무게의 최댓값까지 넣습니다.

 

 

0-1 배낭

---

이 문제는 백준 12865번의 예제를 참고하여 설명하겠습니다.

 

물건을 담았을 때의 가치를 계산할 dp[N][K]배열을 만듭니다.

이 배열의 행은 각 물품의 (무게, 가치), 열은 배낭에 넣을 수 있는 무게를 말합니다.

첫 번째 행은 아무 짐도 넣지 않을 경우이므로 어떠한 무게를 넣을 수 있든 가치가 0입니다.

	0	1	2	3	4	5	6	7
X	0	0	0	0	0	0	0	0
6, 13
4, 8
3, 6
5, 12

 

(6, 13) 짐을 넣으려고 한다면

배낭에 넣을 수 있는 무게 6 이상일 때는 가치가 13입니다.

	0	1	2	3	4	5	6	7
X	0	0	0	0	0	0	0	0
6, 13	0	0	0	0	0	0	13	13
4, 8
3, 6
5, 12

 

(4, 8) 짐을 넣으려고 한다면

배낭에 넣을 수 있는 무게가 4부터 짐을 넣을 수 있습니다.

하지만 무게가 6, 7일 경우에는 (4, 8) 짐을 넣는 것보다 (6, 13) 짐을 넣는 것이 가치가 더 높습니다.

	0	1	2	3	4	5	6	7
X	0	0	0	0	0	0	0	0
6, 13	0	0	0	0	0	0	13	13
4, 8	0	0	0	0	8	8	13	13
3, 6
5, 12

 

(3, 6) 짐을 넣으려고 한다면

배낭에 넣을 수 있는 무게가 3부터 짐을 넣을 수 있습니다.

무게 4, 5일 경우는 (4, 8)인 짐을 그대로 넣고 있는 것이 더 가치가 더 높습니다.

무게 6일 경우는 (6, 13)인 짐을 넣고 있는 것이 더 가치가 높습니다.

무게 7일 경우에는 (4, 8), (3, 6)인 짐을 넣는 것이 가치가 높습니다.

	0	1	2	3	4	5	6	7
X	0	0	0	0	0	0	0	0
6, 13	0	0	0	0	0	0	13	13
4, 8	0	0	0	0	8	8	13	13
3, 6	0	0	0	6	8	8	13	14
5, 12

 

지금까지 계산해본 것을 정리한다면 생각해야 할 부분은 두 가지입니다.

'현재 짐을 넣은 것, 넣지 않은 것 중에 어떤 가치가 더 큰가' 이 말을 다른 말로 바꾸자면

'그전 행에서 현재 짐을 넣을 수 있는 경우에 짐을 넣은 것, 짐을 넣지 않고 그전 행을 가져온 것 중 가치가 큰 것'이라고 생각할 수 있습니다.

 

이 것을 식으로 바꾸자면 이런 식이 됩니다.

dp[ i ][ j ] = max( dp[ i - 1][ j ], dp[i - 1][j - 짐의 무게] + 짐의 가치 ) ( j >= 현재 짐의 무게)

 

 

0-1 배낭 문제 1차원 배열로 풀기

---

현재 공부한 알고리즘 방식은 (현재 행 - 1) 행을 검사하면서 움직이고 있습니다.

이런 방식은 현재 칸의 앞 열들을 이용해서 계산하므로 배열을 1차원으로 만들 경우 이미 갱신된 칸들이 나중의 계산에 영향을 미칠 수 있습니다.

 

그래서 dp배열을 뒤에서부터 연산해준다면 이런 문제를 없앨 수 있습니다.

 

이 알고리즘의 식은 다음과 같습니다.

dp[ j ] = max( dp[ j ], dp[j - 짐의 무게] + 짐의 가치 ) ( j >= 현재 짐의 무게) ( j를 줄여가면서 진행)