[BOJ] 12865 평범한 배낭 - DP(Knapsack 알고리즘)

풀이의 흐름을 기억하고자 적습니다.

Knapsack(냅색) 알고리즘이란?

유명한 패턴의 문제이다.

• 정해진 무게(K)만큼 담을 수 있는 가방이 있고
• 그 안에 담을 수 있는 물건 리스트 N개가 무게(W)와 가치(V) 형태로 주어진다.
• 최대한 높은 가치의 물건들로 왓츠인마이백을 구성하면 된다.

이때 넣는 물건을 분할할 수 있는 (eg. 설탕 나누어 넣기) 배낭 문제를 분할 가능 배낭 문제라 하고,
넣는 물건을 분할할 수 없는, 즉 이 문제처럼 물건을 넣거나 안 넣거나 두 가지 뿐인 배낭 문제를 0-1 배낭 문제라고 한다.

이 문제를 푸는 사고의 흐름은 다음과 같다.

1. 표, 즉 2차원 리스트를 그린다.
   예를 들면 이런 식이다.
   

2. 그리고 가방의 무게를 0부터 K까지, 넣는 물건을 0가지부터 N까지로 나눈 뒤 물건을 가벼운 것부터 하나씩 넣어보는 것이다.
   0을 포함하는 이유는 계산에 직전값이 필요하기 때문이다.

3. 이 2차원 리스트를 순회하면서 값을 채워넣는다.
   N을 x축으로 생각하면서 물건을 하나씩 들고 0부터 K까지의 가방에 넣어본다고 생각하는 것이다.

4. 값을 채우는 방식은 다음과 같다.

   1. 가방의 크기(k) 보다 지금 들고 있는 물건의 무게가 무거울 경우:
      일단 이 물건은 가방에 넣을 수 없다.
      따라서 같은 크기의 물건을 넣었던 직전 가방의 가치값으로 채운다.
   2. 가방의 크기보다 지금 들고 있는 물건의 무게가 같거나 적을 경우:
   • 직전에 넣었던 가방의 가치값과,
   • 현재 들고 있는 물건의 가치값 + 가방의 무게에서 현재 물건의 무게를 뺀 만큼의 가방이 가지고 있는 가치값의 합
     (예를 들어 내가 들고 있는 물건은 5키로인데 가방이 7키로라면,
     5키로짜리 물건의 가치값과 2키로짜리 가방이 가질 수 있는 가치값의 최대값을 합한 것이다.)
     이 둘 중 최대값으로 채운다.

DP 특성상 이전 값을 사용하기 때문에 0 인덱스 부분을 놓치지 않는 것이 포인트라고 생각한다.

풀이

시행착오

알고리즘 초보(=나)는 이 문제를 보고 그리디(Greedy)를 떠올렸다.

# 처음 생각했던 풀이
...
wv = [tuple(map(int,input().split())) for _ in range(N)]

candidate = []	# 후보군
for i in range(N):
    w, v = 0, 0   # (무게, 가치)
    if w+wv[i][0] <= K:
        w, v = w+wv[i][0], v+wv[i][1]
    candidate.append((w, v))
    for j in range(i+1, N):
        if w+wv[j][0] <= K:
            w, v = w+wv[j][0], v+wv[j][1]
        candidate.append((w, v))

print(max(candidate, key=lambda x:x[1])[1])

가치가 높은 순으로 정렬을 해서,
하나씩 가방에 넣어가면서 자리가 남으면 남은 가방 중 무게가 적절한 가방을 모두 넣는다는 내용의 풀이이다.

이렇게 풀면 테스트 케이스는 통과한다.
하지만 이렇게 가방 문제를 그리디로 풀면 그 결과가 최적해를 보장하지 않는다.
가방을 넣었다 뺐다 하면서 최대의 가치를 찾아야 하는데,
내 풀이대로라면 가방을 빼는 과정이 없기 때문이다.

올바른 풀이

위에서 설명한 알고리즘을 파이썬Python으로 구현한 코드는 다음과 같다.

N, K = map(int, input().split())
wv = [tuple(map(int,input().split())) for _ in range(N)]
wv.append((0, 0))
wv.sort(key=lambda x:x[0]) # 무게가 적은 순으로 정렬
case = [[0 for _ in range(K+1)] for _ in range(N+1)]

# DP + 배낭 풀이
for n in range(1,N+1):  # (무게, 가치) 쌍
    for k in range(1,K+1):  # 최대 가방 무게, k는 현재 가방의 무게
        w, v = wv[n][0], wv[n][1]   # 물건을 하나씩 들고 오면서 무게가 0일 때부터 K일 때까지 경우를 파악

        if w <= k:  # 지금 들고 있는 물건이 가방보다 작으면, 넣을 수 있겠지
            case[n][k] = max(case[n-1][k], v+case[n-1][k-w])
        else:
            case[n][k] = case[n-1][k]

print(case[N][K])

결과대로라면 case[N][K]에서 가치가 최대가 됨을 보장할 수 있다.

🍀 결과