https://www.acmicpc.net/problem/14728
1. 문제 개요
- 대표적인 DP 문제인 배낭 문제(Knapsack Problem)이다. 최대 중량이 있는 배낭에 물건을 담을 때, 담은 물건의 가치를 최대로 하면서 배낭의 최대 중량을 초과하지 않도록 해야 한다.
- 배낭 문제는 물건을 분할 가능한 문제(Fractional Knapsack Problem)와 분할 불가능한 문제(0-1 Knapsack Problem)로 나눌 수 있다.
- 이 문제의 경우 배낭은 시험, 중량은 시간, 물건의 가치는 시험 성적, 주어진 물건의 개수는 시험 범위 단원 수로 대응하여 생각할 수 있다.
- 0-1 배낭 문제는 그리디한 방식으로 풀 수 없다. 예를 들어 총 용량이 20kg인 배낭이 있고, 주어진 물건 3가지의 정보가 다음과 같을 때:
{ (10kg, 6000원), (10kg, 3000원), (14kg, 8000원) }, 실제로는 10kg짜리 2개를 담아야 물건의 가치가 최대가 되지만 탐욕법으로 접근하면 14kg 하나만 담고 끝나게 된다.
- 여러 단원을 융합한 문제는 출제하지 않는다.
- 한 단원에 한 문제를 출제한다. 단, 그 단원의 모든 내용을 알고 있어야 풀 수 있는 문제를 낼 것이다.
조건에 따라 이 문제는 0-1 냅색 문제임을 알 수 있다.
0-1 배낭 문제 살펴보기
예제
위키피디아 영문 페이지에서 예제를 가져왔다.
이미지 편집에 wepplication님의 애니메이션 GIF생성기를 사용했다. 감사합니다!
아래 애니메이션은 용량(W, Capacity)이 6인 배낭에 최대 가치로 수납하기 위해 가치가 v이고 무게가 w인 4가지 물건들을 상향식으로 담아보는 과정이다.
먼저 왼쪽의 테이블을 itmes, 오른쪽의 테이블을 knapsack이라고 부르겠다.
items는 이렇게 생겼다고 하자. 튜플은 순서대로 v, w 값이다. 인덱스 접근을 1부터 하려고 0번째 원소를 채웠다.
items = [ (0,0), (5,4), (4,3), (3,2), (2,1) ]knapsack은 다음과 같이 선언한다.
# i=4, W=6
knapsack = [ [0]*(W+1) for _ in range(i+1) ]knapsack[a][b]는 최대 용량이 b인 가방에 a가지 물건을 최적으로 수납했을 때의 상태를 저장하게 된다.
변수를 선언했으니 반복문을 만들어보겠다.
# i=4, W=6
for n in range(1, i+1):
v, w = items[n]
for weight in range(1, W+1):
#TODO
이제 바깥쪽 루프를 기준으로 동작을 살펴보자.
물건을 수납할 수 없을 때 ( weight < w )
먼저 n=0일때와 wegith=0일때는 고려하지 않는다. 어차피 각각 수납할 물건이 하나도 없는 경우와 배낭의 용량이 0일때를 의미하기 때문이다. 때문에 두 루프 모두 1부터 시작한다.
n=1일때 동작을 살펴보자.
n=1이므로 현재 배낭(knapsack[n][weight])에 첫번째 물건을 넣을지 말지를 결정할 것이다.
items[1] = (5,4) 이므로 현재 고려할 물건의 가치는 5, 무게는 4이다.
먼저 애니메이션에서 주황색으로 표시된, weight가 1~3(weight<n_weight)인 구간을 보자.
배낭의 총 용량(현재 남은 용량이라고도 생각할 수 있다)이 현재 넣고자 하는 물건의 무게(w=4)보다 적다면 물건을 넣을 수 없으므로, 직전 상태에서 물건이 추가되지 않은 것과 같다고 볼 수 있다. 따라서 현재 위치에 knapsack[n-1][weight]값을 넣는다. 코드로 표현하면 다음과 같다.
if weight<w:
knapsack[n][weight] = knapsack[n-1][weight]물건을 수납할 수 있을 때 (1)
그렇다면 물건을 수납할 때는 어떻게 해야 할까? n=1, weight=4일 때를 살펴보자.
현재 배낭의 남은 용량(weight)이 넣고자 하는 물건의 용량(w)보다 크거나 같으므로 배낭에 물건을 넣을 수 있다. 물건을 수납할 때에는 수납하는 것이 이득인지 비교가 필요하다.
이 스텝에서는 현재 위치인 knapsack[1][4]외에 knapsack[0][0]에도 하이라이팅이 되어 있는데, 이는 현재 넣고자 하는 물건의 무게(w)가 현재 배낭의 용량(weight)를 4만큼 소모하므로, 나머지 용량만큼의 가치(knapsack[n-1][weight-w])를 의미한다.
물론 아직 물건을 하나도 넣지 못했기 때문에(n=1), 현재는 무조건 물건을 수납하는 것이 전체 배낭의 가치가 올라가므로 이득이다. 비교식은 루프를 좀 더 돌고 난 후에 보충하기로 하고 일단 루프를 채워보겠다.
# i=4, W=6
for n in range(1, i+1):
v, w = items[n]
for weight in range(1, W+1):
if weight<w:
knapsack[n][weight] = knapsack[n-1][weight]
else:
knapsack[n][weight] = knapsack[n-1][weight-w] + v물건을 수납할 수 있을 때 (2)
n=1일때는 물건을 수납할 수 있는 경우 수납하는 것이 무조건 이익이었다. 하지만 물건을 수납하지 않는 것이 이득인 경우도 살펴보자.
다음은 n=2인 경우이다. v=4, w=3이다.
weight>=w인 부분 중 노란색을 보자.
이해를 위해 knapsack[n-1][weight-w]도 표시했다.
이번에는 물건을 수납하지 않는 것이 이득이다. 물건을 수납해봤자 knapsack[n-1][weight-w] + v 가 4라 수납하지 않은 경우(knapsack[n-1][weight])인 5보다 작기 때문이다.
따라서 아까 작성한 코드에 다음과 같이 비교문을 추가해야 한다.
for n in range(1, i+1):
v, w = items[n]
for weight in range(1, W+1):
if weight<w:
knapsack[n][weight] = knapsack[n-1][weight]
else:
knapsack[n][weight] = max(
knapsack[n-1][weight-w] + v,
knapsack[n-1][weight]
)즉 max함수에서 비교하는 두 값은 각각 현재 물건을 수납하는 경우의 가치, 현재 물건을 수납하지 않는 경우의 가치이다.
정리
Bottom-Up으로 배낭에 물건을 수납해보며 dp 테이블에 전체 배낭의 최대 가치를 기록해나간다.
- 현재 물건을 배낭에 수납할 수 없으면 직전 상태를 기록 주황색
- 현재 물건을 배낭에 수납할 수 있으면 다음을 비교
1) 현재 물건의 가치 + 현재 물건 무게 나머지 용량 가치가 더 크면 수납 하늘색
2) 직전 상태가 더 크면 수납하지 않고 직전 상태 기록 노란색
재귀함수나 백트래킹으로도 구현할 수 있다.
전체 동작
n=1
n=2
n=3
n=4
완성된 DP테이블
2. 풀이
import sys
input = lambda: map(int, sys.stdin.readline().split())
N, T = input()
dp = [ [0] * (T+1) for _ in range(N+1) ]
for n in range(1, N+1):
k, s = input()
for t in range(1, T+1):
if t<k:
dp[n][t] = dp[n-1][t]
continue
dp[n][t] = max(dp[n-1][t], s+dp[n-1][t-k])
print(dp[N][T])주어진 입력을 0-1 배낭문제로 풀면 쉽게 해결된다.
이 문제는 입력범위가 크지 않아서 2차원 리스트로 선언해 풀어도 통과되지만, dp테이블을 배열 대신 해시테이블로 구현하면 시간복잡도와 공간복잡도를 크게 개선할 수 있다.
3 310
50 40
100 70
200 150위 입력을 예시로 들면, 단원 개수 N과 공부할 수 있는 총 시간 T가 각각 3과 310으로 주어지기 때문에 dp테이블을 3*310회 순회하게 되지만, 실제로 유의미한 조합은 가지밖에 없기 때문이다.
