백준 12865번 : 평범한 배낭

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

다이나믹 프로그래밍의 기본 유형이라고 할 수 있는 문제이지만, 2차원 리스트를 이용한 메모이제이션을 생각하는 과정과 사소한 실수로 푸는데 시간이 많이 소요됐다.

 

문제를 요약하면 N개의 물건은 각각 무게와 가치를 갖고 있는데, 주어진 배낭의 용량(K)을 넘지 않게 물건을 넣어서 배낭 안에 들어있는 물건들의 가치의 합을 최대로 만드는 문제이다.

 

먼저 시간을 고려하지 않고 문제를 해결하기 위한 방법으로 완전탐색을 생각했다. 1번부터 N번까지 순서대로 각 물건을 넣을지 말지 결정하여 배낭에 넣을 수 있는 물건들의 경우의 수를 모두 구하고, 배낭의 용량을 넘지 않는 경우의 수 중 들어있는 물건의 가치가 최대인 값을 출력한다. 각 물건은 2가지 상태(배낭에 넣거나 말거나)가 존재하므로 경우의 수를 구하는데 걸리는 시간은 O(2^n)이다.

 

재귀를 이용해 완전탐색을 구현하다 보면, i번째 물건을 넣을지 말지 선택하는 함수의 호출이 그때의 배낭 무게에 따라 여러 번 호출된다는 것을 알 수 있다. 당장 i-1번째 물건의 상태만 고려해봐도, i-1번째 물건을 배낭에 넣었다면 배낭의 무게가 증가했을 것이고 넣지 않았다면 배낭의 무게는 그대로 일 것이므로 i번째 물건의 상태를 결정하는 함수가 2번 호출된다. (물론 호출됐을때 배낭의 무게는 각각 다를 것이다.)

 

즉, 완전탐색을 진행하다가 i번째 물건의 상태를 결정할때의 배낭의 무게에 따라 계산한 값을 저장해놓는다면, 이후에 동일한 조건에서 호출이 되더라도 계산하지 않고 저장된 값을 꺼내오면 될 것이다. 어떤 물건의 상태를 결정할때 가능한 배낭의 무게는 [0, k]이므로 2차원 리스트 d[n][k]를 만들어서 값을 저장한다.

 

처음엔 재귀함수의 인자로 물건의 번호(i), 배낭에 가용한 무게(w), 들어있는 물건들의 가치(v)를 넣어서 i가 n을 초과하면 v를 리턴하도록 구현했으나, 이렇게 될 경우 i가 증가할수록 배낭에 들어있는 물건들의 가치가 누적된 상태로 값이 저장되므로 그 값을 다시 사용할 때 의미가 달라진다.

import sys
input = sys.stdin.readline

def sol(i, w):

    if i == n+1:
        return 0

    if d[i][w] >= 0:
        return d[i][w]

    r1 = sol(i+1, w)
    r2 = 0
    if w - s[i][0] >= 0:
        r2 = s[i][1] + sol(i+1, w - s[i][0])

    d[i][w] = max(r1, r2)

    return d[i][w]

n, k = map(int, input().split())
s = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]
d = [[-1]*(k+1) for _ in range(n+1)]
print(sol(1, k))