[알고리즘] 다이나믹 프로그래밍 (문제편 1: 배낭 문제)

다이나믹 프로그래밍 개념은 이전 포스트에서 다뤘다 ([알고리즘] 다이나믹 프로그래밍 (개념) + LeetCode 509)

이번 포스트에서는 대표 문제인 배낭 문제 (Knapsack problem)을 풀어보자 

 

1. 배낭 문제

도둑이 보석가게에 배낭을 매고 침입했는데, 배낭에 최대한 담을 수 있는 무게는 W다 (초과하면 찢어진다고 하자). 보석들의 무게외 값은 미리 알고 있다고 가정하자. 배낭에 담을 수 있는 보석의 최대 가격은?  (편의상 무게는 모두 양의 정수 값을 갖는다고 가정하자.)

 

풀이:

W: 최대 담을 수 있는 무게 (양의 정수)

jewelry = [(p1,w1), (p2,w2),...,(pn,wn)]: 1번에서 n번째 보석들의 값 p와 무게 w (w는 양의 정수)

 

우선 단순무식한 풀이를 생각해보자. 각 보석마다 가방에 넣을까/말까 두 경우가 있을 수 있기 때문에, 모든 가능성을 조사해서 W를 초과하지 않는 최소 값을 구하는 방법을 생각해볼 수 있다. 이런 경우 계산 복잡도는 \( 2^n\)이 되고 매우 비효율적이다.

 

효율적으로 풀기 위해서 다음과 같은 전략으로 접근할 수 있다. 1번 보석에서 n번 보석을 사용해서 W를 초과하지 않도록 최대한 비싼 보석을 담는 문제만 풀지 말고, 그 하위 문제인 1번에서 n'번 보석을 사용해서 W'를 초과하지 않도록 최대한 비싼 보석을 가방에 담는 문제들을 먼저 풀자 (n' < n, W' <= W). 그리고 이 하위 문제들의 해를 사용해서 원래 문제를 풀어보자 (피보나치 수열을 계산하는 문제와 비슷하게).

 

이런 접근방식으로 풀려면, 1번에서 n-1번 보석을 사용해서 무게가 1에서 W까지 최대 값어치를 하는 보석을 담는 방법을 알고 있을 때, n번째 보석을 고려하면 최대 값어치를 갖는 보석을 담는 방법이 어떻게 바뀌어야하는지 알아야한다. 그런데 생각해보면, 1번부터 n-1번 보석을 사용해서 무게 W-wn 를 넘지 않도록 최대한 비싼 보석을 담는 해를 알고 있 때문에, 이 값에 n번째 보석의 값을 더한 값이 n번째 보석을 사용했을 때 최대한 비싼 보석을 담는 방법이 된다. 물론 n번째 보석을 사용한 것보다 1번에서 n-1번까지 보석만 써서 W를 초과하지 않도록 보석을 담는 것이 더 비싼 보석을 담는 방법이 될 수 있기 때문에, 이 둘중 더 큰 값어치를 하는 방식이 해가 되겠다. 

 

태이블로 정리해서 예를 들어보면 이해하기 조금 더 쉬울 것이다 (그림 참고):

• W=5
• jewelry = [(3,3), (2,1), (2,2)].

테이블에 적힌 숫자들은 1번에서 n번째 보석을 사용했을 때 주어진 무게를 초과하지 않으면서 담을 수 있는 최대 보석의 가격이다. 편의상 무게와 가격이 0인 0번째 보석을 도입했다. 테이블을 보면 보석 3개를 모두 고려했을 때 무게가 5를 초과하지 않으면서 담을 수 있는 최대 보석의 가격은 5인 것을 알 수 있다. 

이 테이블을 얻는 방법은 위에 설명한 바와 같고, 예를 들어서 무게가 3을 초과하지 않으면서 3번째 보석까지 고려한 해(빨강색으로 칠해진 숫자)는 다음과 같이 얻는다. 우선 3번째 보석의 무게는 2이므로 보석 1,2번들을 고려해서 최대 무게가 1 (=3-2)이 넘지 않는 해 (파랑색으로 칠해진 숫자)에 2를 더해서 4를 얻는다. 1,2번 보석만 고려해서 무게 3을 넘지 않는 해는 3이기 때문에 (회색으로 칠해진 숫자), 3개의 보석을 고려해서 무게 3을 넘지 않는 최대 보석의 값은 4가 된다.

 

def max_price(jewelry, W):
    # knapsack = 위에서 설명한 테이블
    knapsack = []
    for i in range(len(jewelry)+1):
        knapsack.append([])
        for c in range(W+1):
            if i==0 or c==0:
                # 테이블의 테두리는 0으로 체워준다
                knapsack[i].append(0)
            elif jewelry[i-1][1] <= c:
                # 위에서 설명한 메인 로직
                knapsack[i].append(
                    max(
                        jewelry[i-1][0] + knapsack[i-1][c-jewelry[i-1][1]],
                        knapsack[i-1][c]
                    )
                )
            else:
                # i번째 보석의 무게가 너무 무거우면 i-1번째 해를 사용
                knapsack[i].append(knapsack[i-1][c])
    return knapsack[-1][-1]

참고 자료: 파이썬 알고리즘 인터뷰: 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트