풀이의 흐름을 기억하고자 적습니다.
Knapsack(냅색) 알고리즘이란?
유명한 패턴의 문제이다.
- 정해진 무게(K)만큼 담을 수 있는 가방이 있고
- 그 안에 담을 수 있는 물건 리스트 N개가 무게(W)와 가치(V) 형태로 주어진다.
- 최대한 높은 가치의 물건들로 왓츠인마이백을 구성하면 된다.
이때 넣는 물건을 분할할 수 있는 (eg. 설탕 나누어 넣기) 배낭 문제를 분할 가능 배낭 문제라 하고,
넣는 물건을 분할할 수 없는, 즉 이 문제처럼 물건을 넣거나 안 넣거나 두 가지 뿐인 배낭 문제를 0-1 배낭 문제라고 한다.
이 문제를 푸는 사고의 흐름은 다음과 같다.
-
표, 즉 2차원 리스트를 그린다.
예를 들면 이런 식이다.
-
그리고 가방의 무게를 0부터 K까지, 넣는 물건을 0가지부터 N까지로 나눈 뒤 물건을 가벼운 것부터 하나씩 넣어보는 것이다.
0을 포함하는 이유는 계산에 직전값이 필요하기 때문이다. -
이 2차원 리스트를 순회하면서 값을 채워넣는다.
N을 x축으로 생각하면서 물건을 하나씩 들고 0부터 K까지의 가방에 넣어본다고 생각하는 것이다. -
값을 채우는 방식은 다음과 같다.
- 가방의 크기(k) 보다 지금 들고 있는 물건의 무게가 무거울 경우:
일단 이 물건은 가방에 넣을 수 없다.
따라서 같은 크기의 물건을 넣었던 직전 가방의 가치값으로 채운다. - 가방의 크기보다 지금 들고 있는 물건의 무게가 같거나 적을 경우:
- 직전에 넣었던 가방의 가치값과,
- 현재 들고 있는 물건의 가치값 + 가방의 무게에서 현재 물건의 무게를 뺀 만큼의 가방이 가지고 있는 가치값의 합
(예를 들어 내가 들고 있는 물건은 5키로인데 가방이 7키로라면,
5키로짜리 물건의 가치값과 2키로짜리 가방이 가질 수 있는 가치값의 최대값을 합한 것이다.)
이 둘 중 최대값으로 채운다.
- 가방의 크기(k) 보다 지금 들고 있는 물건의 무게가 무거울 경우:
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]에서 가치가 최대가 됨을 보장할 수 있다.
🍀 결과
