[Dynamic Programming] 배낭 문제(Knapsack Problem)

설명

---

 배낭 문제(Knapsack Problem)는 조합 최적화의 유명한 문제다.

 

 예를 들어 설명해보자. 한 여행가가 여행을 떠나려고 한다. 여행가가 가지고 가는 배낭에는 담을 수 있는 무게의 최댓값이 정해져 있고 배낭에 넣을 수 있는 짐에는 각각의 무게(W)와 가치(V)가 정해져 있다.

 

 이 여행가가 배낭의 무게를 최대한 꽉 채우되 가치의 합이 최대가 되도록 짐을 고르려면 어떻게 해야 할까?

 

 여기서 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우 두 가지로 나눌 수 있다.

 

• 짐을 쪼갤 수 있는 분할 가능 배낭 문제(Fractional Knapsack Problem) - 그리디 알고리즘
• 짐을 쪼갤 수 없는 배낭 문제(Knapsack Problem) - 동적 계획법(Dynamic Programming)

 

 이 글에서는 짐을 쪼갤 수 없는 배낭 문제(Knapsack Problem)를 동적 계획법(Dynamic Programming)을 통해 풀어나가는 과정을 소개하고자 한다.

 

 

 

문제 및 풀이

---

 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다.

세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

 

 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다.

각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다.

아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다.

준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

 

백준 알고리즘 12865번 평범한 배낭 문제
출처: https://www.acmicpc.net/problem/12865

 

12865번: 평범한 배낭

 

 준서가 최대 무게 허용량이 7인 배낭과 다음과 같은 짐들이 있다고 가정하자.

	무게	가치
짐 1	3	6
짐 2	4	8
짐 3	5	12
짐 4	6	13

 

 쉽게 할 수 있는 생각으로는 

1. 짐 4개 중 1개를 골라 최대 가치를 계산
2. 짐 4개 중 2개를 골라 최대 가치를 계산
3. 짐 4개 중 3개를 골라 최대 가치를 계산
4. 짐 4개 중 4개를 골라 최대 가치를 계산
5. 1~4 과정에서 나온 값 중 가장 높은 값이 최대 값

이렇게 생각할 수 있겠으나 해당 방식은 

nC0 + nC1 + ... + nC r = 2^n

와 같은 경우의 수가 나올 수 있고 너무 많은 시간을 소모하게 된다.

 

 

따라서 이전의 결과를 저장해 두고 활용할 수 있는 동적 계획법(Dynamic Programming)을 사용해보자.

 

짐의 번호를 i, 무게를  w, 가치를 나타내는 함수를 Val이라고 해보자.

 

Val(i, w): ~i 번째까지 짐에 대해 배낭의 무게가 w까지 허용됐을 때 최대 가치

 

짐 번호/무게	1	2	3	4	5	6	7
1	0	0
2
3
4

 다음과 같이 보기 쉽게 표를 작성하고 처음부터 작성해 나가 보자, [짐 1]은 무게가 3 가치가 6이다.

[짐 1]만 생각해본다면 배낭의 무게가 2까지는 아무것도 실을 수 없으므로 가치 합을 0으로 적는다.

 

짐 번호/무게	1	2	3	4	5	6	7
1	0	0	6	6	6	6	6
2
3
4

배낭의 무게 3부터는 [짐 1]의 무게가 3이므로 짐 1을 실을 수 있게 된다. 이후에도 짐 1만 있다고 가정한 것이므로 모두 배낭의 무게가 늘어나도 최대 가치는 6이 된다.

 

짐 번호/무게	1	2	3	4	5	6	7
1	0	0	6	6	6	6	6
2	0	0	6	8	8	8	14
3
4

 다음으로 [짐 2]까지 생각해본다면 배낭의 무게가 3까지는 [짐 1]밖에 실을 수 없으므로 위의 결과를 그대로 적어준다.

배낭의 무게 4부터는 [짐 2]를 실을 수 있다.

[짐이 1까지 있었을 때, (배낭의 무게 4 - 짐 2의 무게 4)의 가치] + 짐 2의 가치 = 8
(↑짐 2를 새로 넣은 경우)
or
[짐이 1까지 있었을 때, 배낭의 무게 4의 가치 = 6

배낭의 무게 4에서는 위와 같이 비교해보면 8의 가치가 더 크므로 8을 적어준다.

 

마찬가지로, 배낭의 무게 7에서는

[짐이 1까지 있었을 때, (배낭의 무게 7 - 짐 2의 무게 4)의 가치] + 짐 2의 가치 = 14
(6 + 8 = 14)
or
[짐이 1까지 있었을 때, 배낭의 무게 4의 가치 = 6

14가 6보다 크므로 14를 적어준다.

 

 이와 같은 방법으로 표를 쭉 채워나가면,

짐 번호/무게	1	2	3	4	5	6	7
1	0	0	6	6	6	6	6
2	0	0	6	8	8	8	14
3	0	0	6	8	12	12	14
4	0	0	6	8	12	13	14

와 같은 표가 완성되고 최대 가치는 14라는 것을 구할 수 있다.

 

 

마무리로, 점화식으로 표현하면 다음과 같이 정리할 수 있다.

Val(i, w) = (w >= weight[i]) ? max( Val(i-1,w), Val(i-1,w-weight[i])+value[i] ) : Val(i-1, w)
※ weight[i] = i번째 짐의 무게, value[i] = i번째 짐의 가치

 

 

관련 문제

---

https://cjwoov.tistory.com/56

[C++, Golang] 12865번: 평범한 배낭