[알고리즘] 배낭 문제(0-1 Knapsack Problem)

배낭 문제에 대해서 알아볼까요~?

 

먼저, 많은 알고리즘 중 배낭 문제를 꼽은 이유는 다음과 같다...

 

최근에 응시한 코테에 나왔는데 풀지 못했다. 문제를 보자마자 배낭 문제라는 것을 알았고, 심지어 DP 문제라는 것도 알았다. 하지만 1차원 배열을 써야 하는지, 2차원 배열을 써야하는지 상세한 풀이 방법이 생각나지 않았다.

대충, 점화식의 형태도 기억이 났지만, 결과적으로는 풀지 못했다. 그래서 다시 한 번 공부를 하면서, 다음 번에는 꼭 한 번에 풀 수 있도록 하고자 한다.

 

🔍  배낭 문제란?

배낭 문제는 유한한 용량을 가진 배낭과 여러 개의 물건들이 주어졌을 때, 배낭에 담을 수 있는 물건들의 조합을 찾아 그 가치의 합이 최대가 되도록 하는 문제이다. 각 물건은 고유한 가치와 무게를 가지며, 물건을 쪼개서 넣을 수 없다는 제약(0-1 제약 조건)이 있다.

 

따라서, 각 물건은 배낭에 넣거나 넣지 않는 두 가지 선택만 가능하다.

 

보석을 자를 수 있는 Fractional KnapSack Problem의 경우에는 Greedy로 접근하면 된다.

하지만, 해당 문제는 물건을 쪼개서 넣을 수 없다는 제약이 존재하므로 다른 방식으로 접근해야 한다.

 

🔑 DP로 배낭 문제 해결하기

다음 점화식으로 배낭 문제를 일반화할 수 있다.

 

\[P[i][w]=\left\{\begin{matrix} 
maximum(P[i-1][w], p_i + P[i-1][w-w_i]) & w_i \leq w\\ 
P[i-1][w] & w_i > w \\ 
\end{matrix}\right.\]

 

위 점화식은 물건을 가방에 넣을 수 있는 경우와 물건을 가방에 넣을 수 없는 경우로 나뉜다.

• 물건을 가방에 넣을 수 있는 경우
  • 즉, 현재 가방의 무게가 물건의 무게보다 크다면, 물건을 넣었을 때와 넣지 않았을 때를 비교해서 MAX 값을 대입해주면 된다.
• 물건을 가방에 넣을 수 없는 경우
  • 즉, 현재 가방의 무게가 물건의 무게보다 작다면, 이전 값을 가져와 대입하면 된다.

 

▶️ 백준 문제로 이해하기

백준-평범한 배낭 문제를 통해 다시 한 번 이해해보자.

실제 예제를 통해 DP 표를 채워나가며 문제를 이해해보자.

 

먼저, 가방에 담을 수 있는 최대 무게는 7이다. 물건은 (무게, 가치)가 각각 (6, 13) (4, 8) (3, 6) (5, 12)인 4개의 물건이 존재한다.

• DP 표를 아래와 같이 그리고, 가방의 무게가 0인 경우 아무것도 채울 수 없으므로 0을 대입해준다.

 

• 이후, 한 칸씩 점화식에 따라 채워나간다. 첫 번재 물건은 무게가 6이므로, 현재 가방의 무게가 1인 상태에서는 담을 수 없다. 따라서 이전 값을 넣어준다.

 

• 현재 가방의 무게(w)가 6이 될 때, 현재 물건을 담을 수 있게 된다. 따라서, 해당 물건의 가치인 13을 채워넣어준다.

 

• 현재 가방의 무게가 7인 경우에는 더 이상 담을 물건이 없으므로 이전 값을 그대로 대입해준다.

 

• 두 번째 물건의 경우에도 동일하게 표를 채워준다.

 

• 현재 가방의 무게가 6인 경우, 두 번째 물건을 넣을 때보다 첫 번째 물건을 넣는 것이 가치가 더 크다. 따라서 이전 물건의 가치인 13을 넣어줘야 한다.

 

• 표에 모든 값을 채워준 후, 마지막에 들어간 값이 담을 수 있는 물건의 최대 가치가 된다. 따라서 해당 예제의 결과는 14이다.

 

 

위 백준 문제의 전체 코드는 다음과 같다.

N, K = map(int, input().split())

bag = []
for _ in range(N):
    w, v = map(int, input().split())
    bag.append((w, v))

dp = [[0]*(N+1) for _ in range(K+1)]

for k in range(1, K+1):
    for i in range(1, N+1):
        w, v = bag[i-1]
        if w <= k:
            dp[k][i] = max(dp[k][i-1], dp[k-w][i-1]+v)
        else:
            dp[k][i] = dp[k][i-1]

print(dp[K][N])