알고리즘 - 배낭문제 (Knapsack problem) (백준 12865 - 평범한 배낭)

이번 알고리즘 스터디에서는 이분탐색과 동적계획법을 주제로 스터디를 진행하였다.

선정한 문제들이 나에게는 너무 어려워 자력으로 해결한 문제가 거의 없었다... 해결한 문제 역시 여러 풀이를 찾아보며 해결했는데, 이 과정에서 이분탐색/동적계획법 외의 많은 알고리즘 기법들 역시 배울 수 있었다.

 

동적 계획법의 인상적인 풀이방법도 배우게 되어 복습하고자 한다.

백준 12865 평범한 배낭 https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

동적 계획법의 대표적 분류인 배낭 문제는 '0-1 배낭문제' 혹은 평이한 배낭문제로 분류된다고 수업에서 배웠다.

평이한 배낭문제의 경우 그리디한 방법으로 단위당 가치 순으로 물건을 담으면 쉽게 해결할 수 있었다만, '0-1 배낭문제'의 경우 np-complete에 해당되는 어려운 문제라고 배웠기에 백준에서 이 문제를 마주치곤 적잖이 당황하였다.

 

어떠한 그리디한 방법도 올바른 해를 보장하지 못하기에, 모든 경우의 수를 따져야만 한다.

이 부분에서 좀 더 쉬운 접근법으로 조합을 이용해 모든 경우의 수를 따져보는 방법이 가장 먼저 떠올랐지만

이는 메모리와 수행 시간 측면에서 상당히 불리한 것이기에, 다른 방법을 떠올리려 했다.

 

가장 효율적인 방법은 동적계획법이었다. 각 물건마다 배낭에 포함된 경우, 그렇지 않은 경우로 나누어 이를 재귀적으로 호출한다. 그 과정에서 이미 계산한 수치를 메모이제이션을 통해 저장하고 호출하여 중복 계산을 줄인다는 것이 주된 아이디어였다.

 

n,k = map(int,input().split())

li = []

v = []
w = []

d = [[0 for _ in range(k+1)] for _ in range(n+1)]

for _ in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)

def search(num,weight):

    if d[num][weight] > 0:
        return d[num][weight]

    if num == n:
        return 0

    include = 0
    if weight + w[num] <= k:
        include = v[num] + search(num+1,weight+w[num])
    exclude = search(num+1,weight)       

    d[num][weight] = max(include,exclude)
    return d[num][weight]

print(search(0,0))

재귀함수 search는 현재 계산중인 물건의 인덱스 num과 현재까지 담은 총 무게 weight를 인자로 받는다.

현재 num의 물건을 배낭에 포함했을 경우 총 가치 include, 포함하지 않았을 경우 총 가치 exclude를 비교하여 반환한다. include의 경우 현재 num의 물건의 가치 v[num]을 더해야하고 현재까지의 무게 역시 현재 num물건의 무게 w[num]을 더해 전달해준다. include와 exclude 중 더 큰 값은 동적계획법을 위한 배열에 저장해 같은 값을 한번 더 필요하게 되었을 시 배열에서 바로 불러올 수 있게 한다.

 

이를 통해 모든 물건마다 2개의 경우(포함,미포함)을 계산하는 2^n의 연산을 보다 효울적으로 할 수 있게 된다.

동적계획법의 경우 탑다운, 바텀업에서의 전형적인 형태로만 접해왔는데 이런 식으로 응용이 가능하다는 것을 처음 알게 되었다.