Q. 도둑이 보석가게에 배낭을 메고 침입했다.
배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다.
각 보석들의 무게(w)와 가격(v)은 알고 있다.
배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?
배낭문제의 종류
배낭문제는 가정에 따라 풀이에 사용하는 알고리즘이 다르다.
- Fractional Knapsack Problem : 보석을 자를 수 있다고 가정
=> Greedy - 0-1 Knapsack Problem : 보석을 자를 수 없다고 가정 (<- 이쪽이 더 자주 다루어짐)
=> DP
👜 Fractional Knapsack Problem (Greedy)
보석의 가치를 "무게 1당 가격"으로 나타낸다.
이 가치가 가장 높은 보석부터 차례대로 배낭의 최대용량을 넘지않을만큼 꽉 채워 담으면 된다.
🍄 무게 당 가격이 가장 높은 보석을 가능한 많이 담는다 🍄
💎 0-1 Knapsack Problem (DP)
보석을 자를 수 없을 때는 탐욕법으로 풀 수 없고, DP를 사용해서 풀어야 한다. (귀찮..)
(1) 동작원리
우리가 구해야하는 것은 "배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법"이므로, 집합 A를 "n개의 보석 중에서 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 담은 부분집합(=최적으로 고른 부분집합)"이라고 해보자.
이 경우에는 n번째 보석을 담거나/담지않는 2가지 선택만이 존재하므로, 각 경우를 나누어서 정리하면 다음과 같다.
- 집합 A에 n번째 보석이 포함되지 않는다면, 집합 A는 나머지 n-1개의 보석들 중에서 최적으로 고른 부분집합과 동일하다.
- 집합 A에 n번째 보석이 포함된다면, 집합 A는 나머지 n-1개의 보석들 중에서 최적으로 고른 부분집합에 n번째 보석을 더한 부분집합과 같다.
※ n번째 보석을 담았을때 배낭이 터지지 않아야 한다. ※
(2) 점화식
이를 점화식으로 나타내면 다음과 같다.
P[i,w]= i개의 보석이 있고, 배낭의 무게한도가 w일때 최적의 이익
cf) 보석은 1~i까지만 있고, 배낭의 "임시"무게한도가 w라고 가정하고 값을 채워나감wi(wk) = i번째 보석의 무게 (왜 wk인지는 아직 모르겠다)vi= i번째 보석의 가격
(3) 점화식에 기반한 동작원리 설명
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) 중에서 큰 값을 선택한다.
(4) 그림으로 보는 동작과정
-
예시 데이터
-
위의 설명에서
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까지
-
최종결과
(5) 코드 (평범한 배낭)
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문 돌리기!
