[Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용

 

Knapsack problem

어떤 물건들의 집합이 주어졌을 때, 가방에 담을 수 있는 최대 가치의 물건들의 집합을 결정하는 문제

Knapsack problem은 크게 2가지 유형이 있다. 

• 0/1 knapsack problem
• Fractional knapsack problem

(a)가 문제상황이다. (b)와 달리 (c)는 물건을 쪼개서 (20/30) 가방에 넣었다. 이렇게 쪼갤 수 있는 경우를 Fractional problem, 그러지 못하는 상황을 0/1 knapsack problem이라고 한다. 

오늘은 이 중 Dynamic programming으로 해결할 수 있는 0/1 knapsack problem에 대해 자세히 알아보겠다.

 

2023.06.08 - [Computer Science/Data structure & Algorithm] - [Algorithm] Knapsack algorithm - Greedy 사용

[Algorithm] Knapsack algorithm - Greedy 사용

(Fractional knapsack problem에 대해 알고 싶으면 위 글을 참고해라)

 

0/1 knapsack problem 

문제 상황

당신은 크기가 W인 가방과  n개의 물건을 가지고 있다.  각 물건은 하나씩 존재한다. 
각 물건 i는 크기 Wi와 가치 Vi를 가지고 있다. 
당신이 이 가방에 물건을 담으려고 할 때,  가방에 담을 수 있는 물건들의 가치의 합이 최대가 되도록 하려면 어떤 물건들을 선택해야할까?
(단, 가방에 담지 못하는 물건이 있을 수 있다.)

해결 방법

dp[n][W] (n: 물건의 개수, W: 가방의 크기) 를 선언한다. dp[i][j]는 1 ~ i까지의 물건을 고려했을 때 크기가 j인 가방에 넣을 수 있는 최대 가치의 합을 저장할 것이다. 

1. 물건들을 크기에 따라 정렬한다. 
2. dp[i][j] 는 물건 1부터 i까지 고려했을 때, 크기가 j인 가방에 넣을 수 있는 물건들의 최대가치 합으로 정의한다.
3. 각 물건의 선택여부에 따라 작은 부분으로 나눈다.
   3-1) 물건 i를 선택하지 않는 경우, dp[i][j] = dp[i-1][j]와 같다. (크기의 변화가 없기 때문이다.)
   3-2) 물건 i를 선택한 경우 dp[i][j] = dp[i-1][j-Wi] + vi와 같다. 이것은 물건 i를 제외한 이전 물건들 중 크기가 j-wi인 가방에 넣을 수 있는 최대 가치 합에 물건 i의 가치 vi를 더한 값과 같다.
4. 최종적으로 dp[n][W]가 가방에 넣을 수 있는 물건들의 최대가치 합이 된다.

 

예제 풀이

7개의 물건이 있다. 물건 각각의 w와 v(아래 예제에서는 p)는 아래와 같다. 

가방의 총 용량이 7이라고 할 때, 어떻게 선택해야 최적의 이익을 얻을 수 있을까?

dp[n][W]를 우선 만들자. 이 문제에서 n = 4, W = 8이니 n+1, W+1 칸의 배열을 생성한다. 그리고 0번물건의 값을 모두 0으로 채우고 가치가 0인 부분도 0으로 채운다. 

물건 | 가치	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0
2	0
3	0
4	0

 

현재 주어진 물건은 이미 w에 따라 정렬이 되어있지만, 그렇지 않은 경우에는 정렬을 해주어야한다. 그 뒤 물건 1 ~ 4를 순회하면서 가방에 넣을 수 있는지 판단해야한다.

[1번 물건]

가방에 물건을 넣을 수도 있고 넣지 않을 수도 있다는 것을 생각하며 예제를 진행시켜보자.

1번 물건의 가치는 2(V1=2)이다.

- 물건을 넣지 않을 경우
dp[1][1] = dp[1][0] = 0

- 물건을 넣을 경우
dp[1][1] = dp[1-1][1-W1] + V1 = dp[0][-1] + V1

물건을 넣을 경우를 살펴보면 index가 음수가 된다. 이 경우는 0이라고 생각하고 비교하면 된다. 그래서 0이 최종 선택이 된다. 

물건 | 가치	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0
2	0
3	0
4	0

 

같은 공식을 적용하면 아래와 같다.

dp[1][2] = max(dp[0][2], dp[0][2-2] + 1) = dp[0][0] + 1 = 1
dp[1][3] = max(dp[0][3], dp[0][3-2] + 1) = dp[0][1] + 1 = 1
dp[1][4] = max(dp[0][4], dp[0][4-2] + 1) = dp[0][2] + 1 = 1
dp[1][5] = max(dp[0][5], dp[0][5-2] + 1) = dp[0][3] + 1 = 1
dp[1][6] = max(dp[0][6], dp[0][6-2] + 1) = dp[0][4] + 1 = 1
dp[1][7] = max(dp[0][7], dp[0][7-2] + 1) = dp[0][5] + 1 = 1

물건 | 가치	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	1	1	1	1	1	1
2	0
3	0
4	0

 

[2번 물건]

2번 물건의 가치는 2이고, 무게는 3이다. (V2 = 2, W2 = 3)

dp[2][1] = max(dp[1][1], dp[1][-2]) = 0
dp[2][2] = max(dp[1][2], dp[1][-1]) = 1
dp[2][3] = max(dp[1][3], dp[1][0]+2) = 2
dp[2][4] = max(dp[1][4], dp[1][1]+2) = 2

...

나머지 물건에 대해 이런 방식으로 채워나가면 된다.

 

물건 | 가치	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	1	1	1	1	1	1
2	0	0	1	2	2	3	3	3
3	0	0	1	2	5	5	6	7
4	0	0	1	2	5	6	6	7

 

그래서 가방에 넣을 수 있는 물건의 최대 가치 합은 dp[4][7] 값인 7이 된다.

위의 식을 정리하면 위와 같다.

 

관련 문제