Q. 도둑이 보석가게에 배낭을 메고 침입했다.
배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다.
각 보석들의 무게(w)와 가격(v)은 알고 있다.
배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?
배낭문제는 가정에 따라 풀이에 사용하는 알고리즘이 다르다.
보석의 가치를 "무게 1당 가격"으로 나타낸다.
이 가치가 가장 높은 보석부터 차례대로 배낭의 최대용량을 넘지않을만큼 꽉 채워 담으면 된다.
🍄 무게 당 가격이 가장 높은 보석을 가능한 많이 담는다 🍄
보석을 자를 수 없을 때는 탐욕법으로 풀 수 없고, DP를 사용해서 풀어야 한다. (귀찮..)
우리가 구해야하는 것은 "배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법"이므로, 집합 A를 "n개의 보석 중에서 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 담은 부분집합(=최적으로 고른 부분집합)"이라고 해보자.
이 경우에는 n번째 보석을 담거나/담지않는 2가지 선택만이 존재하므로, 각 경우를 나누어서 정리하면 다음과 같다.
이를 점화식으로 나타내면 다음과 같다.
P[i,w]
= i개의 보석이 있고, 배낭의 무게한도가 w일때 최적의 이익wi
(wk
) = i번째 보석의 무게 (왜 wk인지는 아직 모르겠다)vi
= i번째 보석의 가격i번째 보석의 무게가 배낭의 무게한도보다 크다면(wi
> w
) 아예 담을 수 없다.
이때의 최적값은 이전 i-1
개의 보석들을 무게한도 w
인 배낭에 넣은 최대값(P[i-1,w]
)과 같다.
하지만 i번째 보석의 무게가 배낭의 무게한도보다 작다면(wi
<= w
), 담거나/담지않거나 중에서 선택할 수 있다.
i번째 보석을 담았을 때 최적값은 배낭의 무게한도 w
에서 i
번째 보석의 무게만큼 자리를 비워두고 나머지 i-1
개의 보석들을 최대로 넣은 값(P[i-1,w-wk]
)에 i번째 보석의 가격(vi
)을 더한 값이다.
i번째 보석을 담지 않았을 때 최적값은 이전 i-1개의 보석들을 무게한도 w인 배낭에 넣은 최대값(P[i-1,w]
)과 같다.
=> 보석의 합이 최대가 되어야 하므로 (1), (2) 중에서 큰 값을 선택한다.
예시 데이터
위의 설명에서 P
에 해당하는 2차원배열이다.
i=0, w=0일때는 모두 0으로 초기화한다.
i=1일때, w=0~10까지
i=2일때, w=0~10까지
i=3일때, w=0~10까지
i=4일때, w=0~10까지
최종결과
N, K = map(int, input().split())
things = [(0,0)]
P = [[0 for _ in range(K+1)] for _ in range(N+1)]
for _ in range(N):
W, V = map(int, input().split())
things.append((W,V))
for i in range(1, N+1):
w = things[i][0]
v = things[i][1]
for j in range(1, K+1):
if w > j:
P[i][j] = P[i-1][j]
else:
P[i][j] = max(P[i-1][j-w] + v, P[i-1][j])
print(P[-1][-1])
💡 enumerate와 인덱스가 안맞을때는 인덱스로만 for문 돌리기!