[DP] Knapsack Problem

최근에 백준에서 다이나믹 프로그래밍(DP)를 공부하다가 처음 보는 유형의 문제가 있어 글을 쓰게 되었습니다.

 

[ 관련 문제 : 백준 12865 평범한 배낭 www.acmicpc.net/problem/12865 ]

 

Knapsack 문제란?

출처 : 위키피디아

어떤 도둑이 보석상에 들어가 보석을 훔친다고 했을 때,

배낭의 용량을 넘치지 않게 담아야 하고, ( 넘치면 훔칠 수 없다는 가정 )

돈을 가장 많이 벌 수 있도록 담는 방법에 대해 얘기하는 것을 Knapsack 문제라고 합니다.

 

Knapsack 문제의 경우는 담는 물건이 나눌 수 있는  경우, 단순하게 담을 수 있냐 없냐 (0-1) 두 가지의 종류가 있지만

지금은 단순하게 담는 0-1 Knapsack 문제에 대해 쓰겠습니다.

 

이게 DP랑 무슨 상관??

단순하게 생각해보면 완전탐색을 이용해 가능한 모든 경우를 고려해볼 수 있겠으나, 

O(n) = 2^n 개가 되어, 개수가 클수록 기하급수적으로 늘어나 이 방법은 너무 오래 걸립니다.

 

비싼 순서대로 담는다고 가정하면 비싸지만 하나밖에 안들어가는 경우,

가격은 조금 싸지만 여러 개를 담는 경우를 비교했을 때 최대한의 이익을 얻을진 보장하기 어렵습니다.

 

문제를 잘게 쪼개서, 해당 순간의 최적 해를 구해나가는 동적 프로그래밍 방식으로 해보면 어떨까요??

동적 프로그래밍 방식이 Memorization을 이용해 시간도 짧고, 나름의 알고리즘(점화식)으로 풀어나가면

시간이 급한 도둑에게 최고의 선물(?)을 해줄 수 있게 됩니다

 

그래서 어떻게 풀건데??

도둑(컴퓨터) 입장이 되어 생각을 해봅시다.

도둑 입장에선 가방에 물건을 많이 넣을 수록 좋겠지만, 넣을지 안 넣을지의 선택만 있습니다.

 

1. 처음 물건을 보고 가방에 들어갈 수 있는 무게인지 판별합니다.

들어갈 수 있으면 일단 넣습니다.

2. 다음 물건이 오면 가방에 넣을 수 있는지 판별하고,

이 물건을 넣었을 때의 가격과 안 넣었을 때의 가격이 어떤지에 따라 넣을지 결정합니다.

3. 2의 과정을 물건을 다 채울 때까지 반복합니다.

 

아래는 12865번 문제에 knapsack 알고리즘을 적용한 예시입니다.

n, k = map(int, input().split()) 
dp = [[0]*(k+1) for i in range(n+1)]
item = [[0, 0]]
for i in range(n):
    item.append(list(map(int, input().split())))
for i in range(1, n+1):
    for j in range(1, k+1):
        if j>= item[i][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[n][k])

 

저는 아래의 블로그를 참조하여 공부하였습니다.

gsmesie692.tistory.com/113

suri78.tistory.com/2