문제 링크: https://www.acmicpc.net/problem/12865

Thumbnail: Photo by Jakob Owens (Unsplash)

DP로 풀 수 있는 0-1 배낭 문제입니다.

풀이

배낭 문제 (Knapsack Problem)

이 문제는 배낭 문제입니다. 배낭 문제는 크게 2가지로 나뉩니다.

• Fractional Knapsack
  • 물건을 쪼개어 넣을 수 있는 배낭 문제입니다.
  • 탐욕법(그리디)로 풀 수 있습니다.
• 0-1 Knapsack
  • 물건을 쪼갤 수 없는 배낭 문제입니다.
  • 탐욕법(그리디)로는 풀 수 없고, DP를 사용해야 합니다.

이번 문제는 0-1 배낭 문제로, DP를 사용해 풀었습니다.

0-1 배낭 문제 아이디어

현재 \(K\)kg만큼의 무게를 더 담을 수 있는 가방이 있습니다. \(N\)개의 물건 중에서 적절히 골라서 배낭에 담으려 할 때, \(i\)번째 물건의 무게를 \(W_i\)kg, 가치를 \(V_i\)라고 합시다.

점화식을 찾기에 앞서, DP 배열을 먼저 정의해야 합니다. 이번 풀이에서 경우의 수를 고민할 때 사용되는 변수는 '배낭에 남은 여유 공간(무게)'와 '현재 탐색하는 물건의 번호 \(i\)'입니다.

앞서 \(i\)번째 물건에 대해 2가지 경우로 나누어 생각했던 부분을 코드로 구현하면 됩니다.

1) \(K < W_i\)

\(i\)번째 물건은 현재 배낭에 넣을 수 없습니다. 이 경우, \(i-1\)번째 물건까지 탐색했을 때와 배낭의 총 가치가 동일합니다.

dp[i][K] = dp[i-1][K]

2) \(K \ge W_i\)

이 경우, 2가지 경우 중 최적의 경우를 계산하면 됩니다.

1. \(i\)번째 물건을 배낭에 담는다.
   이 경우, 배낭의 남은 공간(무게)는 \(W_i\)만큼 감소하며, 총 가치는 \(V_i\)만큼 증가합니다.
2. \(i\)번째 물건을 배낭에 담지 않는다.
   이 경우, \(i-1\)번째 물건까지 탐색했을 때와 배낭의 총 가치는 동일하다.

이 과정을 \(N\)개의 물건에 대해서, 배낭의 여유 무게가 0일 때 부터 K일 때 까지 모두 계산해주면 됩니다.

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

for i in range(1, N + 1):
    weight, value = items[i - 1]
    for w in range(K + 1):
        if weight <= w: # 가방에 현재 물건을 담을 수 있는 경우.
            # 현재 물건을 담지 않는 경우와 담는 경우 중 최대값을 선택
            dp[i][w] = max(dp[i-1][w], value + dp[i-1][w-weight])
        else: # 가방에 현재 물건을 담을 수 없는 경우.
            dp[i][w] = dp[i-1][w]

어떤 문제를 DP로 풀기 위해서는 아래 2가지 조건이 성립해야 합니다.

1. 이 문제가 겹치는 부분 문제를 가지는가?
2. 이 문제가 최적 부분 구조를 가지는가?

앞서 작성한 DP 코드를 보면, 이전 부분 문제를 재활용해 계산에 사용하고 있습니다. 즉, 부분 문제의 최적 해답을 사용해 본래의 문제의 해답을 계산한 게 최적 해답이 된다는 이야기이며, 이 문제가 최적 부분 구조를 가진다는 뜻입니다.
또, DP배열에 이전 부분 문제의 답을 저장하고 재활용하는 것은 겹치는 부분 문제를 가진다는 뜻입니다.
따라서, 이 문제는 DP로 풀기 위한 조건을 모두 충족합니다!

전체 코드

input = open(0).readline
N, K = map(int, input().split())
items = tuple(tuple(map(int, input().split())) for _ in range(N))

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

for i in range(1, N + 1):
    weight, value = items[i - 1]
    for w in range(K + 1):
        if weight <= w: # 가방에 현재 물건을 담을 수 있는 경우.
            # 현재 물건을 담지 않는 경우와 담는 경우 중 최대값을 선택
            dp[i][w] = max(dp[i-1][w], value + dp[i-1][w-weight])
        else: # 가방에 현재 물건을 담을 수 없는 경우.
            dp[i][w] = dp[i-1][w]

print(dp[N][K])