배낭문제(knapsack problem)

배낭 문제(knapsack problem)는 조합 최적화 문제의 일종이다. 간략하게 말하자면, 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제이다.

 

예를 들어 15kg의 무게제한이 있는 배낭에 12kg, 2kg, 1kg를 넣으면 그 가치는 7달러가 된다. 하지만 4kg 물건만 넣더라도 10달러를넘으니 앞의 예시는 가치가 최대가 되는 예가 아닌것이다.

 

브루투포스로 풀면 각 아이템이 ‘있고/없고’ 인 수열로 나타낼 수 있으니 총 시간복잡도는 2^4일 것이다. 하지만 아이템의 개수가 많아진다면 시간복잡도는 2^n으로 증가하니 좋지못한 방법임엔 분명하다.

 

배낭문제는 가치가 최대가 되는 물건들을 고르는 문제임으로, 최적화 문제라고 볼 수 있다. 최적화 문제는 DP(동적계획법)를 먼저 의심해 봐야한다!

 

간단한 예시를 통해 동적계획법을 적용해보자.

 

배낭의 무게제한이 5kg일때 다음과 같은 아이템들이 있다.

	A	B	C	D
가치	30	20	40	10
무게	1	2	3	4

무게제한이 5일 때 4개의 물건들 중, 최대가치를 만드는 문제는 다음과 같이 나타낼수 있다.

 

 NS(’ABCD’, 5)

 

동적계획법의 기본 아이디어는 메인 문제를 서브 문제로 쪼개어 값을 구한 후 메인 문제를 해결하는데 다시 사용하는 것이다.

위 문제는 다시 D가 배낭에 있는 경우, 없는 경우로 쪼갤 수 있다.

 

D가 배낭에 있는 경우: D 무게 4를 빼고 가치 10을 더해준다.

 

NS(’ABC’, 1) ⇒ 가치+10

 

D가 배낭에 없는 경우: 무게와 가치에는 변화가 생기지 않는다.

 

NS(’ABC’, 5) ⇒ 가치+0

 

또한 쪼개진 가운데, 또 다시 C가 있는경우, 없는 경우로 나눌 수 있다. 각각 두 개의 분기점(D가 있는경우, 없는경우)에서 또 다시 두 개가 만들어져 총 4개의 C가 있는경우, 없는경우로 나뉘게 된다.

 

참고로 무게 4인 D가 있는 경우에서는 가방의 무게제한이 5이므로 넣는다면 1밖에 남지 않았으므로 무게가 3인 C는 포함할 수 없게된다.

 

NS(’ABC’, 1) → NS(’AB’, -2) 불가능

 

이렇게 재귀적으로 문제를 쪼개고, 그 값들을 사용해 메인 문제를 해결할 수 있다.

 

위 방식은 점화식으로도 나타낼 수 있다.

N번까지 물건이 있고 현재 상태의 무게제한이 W일 때 최대 가치를 구하는 점화식은 다음과 같다. W는 가방의 무게제한, w[n]은 물건 n의 무게, p[n]은 물건n의 가치이다.

 

NS(N, W) = max( NS(N-1, W) + 0, NS(N-1, W-w[n] + p[n] )

 

그리고 이렇게 계산한 값들을 저장하는 테이블 DP를 만들어 보자. 이 문제의 경우 변수가 N, W 두개로 2차원 테이블이 필요함을 알 수 있다. 2차원 배열에서 행은 배낭에 넣을 수 있는 물건들을 나타내고 열에는 배낭의 무게제한을 나타낸다.

 

여기서 우리는 4개의 물건들 중 무게제한이 5일때 최대 가치를 찾아야하므로 DP[4][5]의 값이 필요하다.

 

우선 물건이 없을 때는 그 가치 또한 0임으로 DP[0][0~5]까지 0으로 초기화 시켜준다. 그리고 물건들이 있더라도 가방의 무게제한이 0이라면 그 가치 또한 0이 되므로 DP[0~4][0] = 0으로 초기화 시켜주자.

 

	0	1	2	3	4	5
-	0	0	0	0	0	0
1 (A)	0
2 (A, B)	0
3 (A, B, C)	0
4 (A, B, C, D)	0

 

이제 바텀업 방식으로 칸들을 채워나가 보자.

 

먼저 A 하나만 있는 케이스를 살펴보자.

A가 있을 때 가치와 없을 때 가치를 비교해 큰 값을 다음과 같이 배열에 채워준다. 먼저 물건 A의 무게는 1임으로, 1열 부터 물건을 넣을 수 있다. 그리고 물건들중 A 하나만 있을 때 아무것도 넣지지 않으면 가치가 0이므로 max(30, 0)으로 1행 1열부터 5열까지는 30으로 채워진다

	0	1	2	3	4	5
-	0	0	0	0	0	0
1 (A)	0	30	30	30	30	30
2 (A, B)	0
3 (A, B, C)	0
4 (A, B, C, D)	0

 

이제 A, B가 있는 케이스를 살펴보자.

물건을 넣을때는 두 가지의 경우의수가 생기는데 그 경우는 아래와 같다.

1) B의 무게는 2이므로 무게제한이 2미만인 케이스에 대해서는 B를 선택할 수 가 없다. 그래서 DP[1][1]의 값을 가져온다.

 

2) 그리고 무게제한이 2 이상인 지점(2열 이상)에는 1행과(A,B 물건이 있는 행) 현재 열 인덱스에서 B의 무게를 뺀 위치의 값들 (EX. 현재 2열에 있는경우, 2 - 2 → DP[1][0], 현재 3열에 있는 경우, 3 - 2 → DP[1][1], …)의 가치에 B의 가치를 더해준 값과 B를 선택하지 않았을 경우의(바로 위의 행) 값들을 비교해서 큰 값으로 넣어준다.

NS[2][2]의 경우 30(B를 선택하지 않은 경우)과 20(0 + 20 A를 선택하지않고 B만 선택한 경우) 을 비교해서 큰 값인 30을 넣어준다. (NS[1][0] + 20 < NS[1][1] 이므로)

	0	1	2	3	4	5
-	0	0	0	0	0	0
1 (A)	0	30	30	30	30	30
2 (A, B)	0	30	30	50	50	50
3 (A, B, C)	0
4 (A, B, C, D)	0

 

이제 위 과정을 계속 반복해 DP[4][5]의 값을 구해 최적 해를 찾아낼 수 있다.

 

	0	1	2	3	4	5
-	0	0	0	0	0	0
1 (A)	0	30	30	30	30	30
2 (A, B)	0	30	30	50	50	50
3 (A, B, C)	0	30	30	50	70	70
4 (A, B, C, D)	0	30	30	50	70	70

---

해당 방법을 사용해서 밑의 문제를 해결 해 보자!

 

12865번: 평범한 배낭

12865번: 평범한 배낭

 

무게제한, 가치 등 설명한 방법 그대로인 문제이다!

# 평범한 배낭
import sys

n, k = map(int, sys.stdin.readline().split())
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
items = [(0,0)]

for i in range(n):
    w, p = map(int, sys.stdin.readline().split())
    # 무게와 가치 튜플로 저장해 준다.
    items.append((w, p))

# 행은 넣을 수 있는 물건을, 열은 가방의 무게제한을 의미한다.
for i in range(1, n+1):
    for j in range(1, k+1):
        # 현재 물건의 무게가 무게제한 보다 작거나 같을 때는 물건을 넣는경우와
        # 물건을 넣지않는 경우의 가치를 비교해서 큰 값을 넣어준다.
        if j >= items[i][0]:
            dp[i][j] = max(dp[i-1][j-items[i][0]] + items[i][1], dp[i-1][j])
        # 현재물건의 무게가 무게제한보다 크다면 해당 물건을 넣지 않는다.
        else:
            dp[i][j] = dp[i-1][j]

print(dp[n][k])

 

동적계획법의 대표격 문제라고 할 수 있는 배낭 문제를 다뤄봤다. 2차원 배열을 쓰는 동적계획법은 많으므로 이 문제에 익숙해 진다면 2차원 배열을 사용하는 다른 동적계획법 문제도 점화식을 찾아 낼 수 있을것이다!