[백준] 12865 평범한 배낭 - 동적계획법과 냅색(Knapsack)

짐 싸기 문제(가방에 물건을 담는 케이스)는 동적 계획법으로 해결할 수 있는 경우가 많습니다.

여러 물건이 있을 때, 특정한 조건을 만족하는 조합을 구하는 문제입니다.

 

대표적인 문제로는 백준 12865 평범한 배낭 문제가 있습니다.

 

---

• 물건의 무게(W)와 가치(V)가 주어지고, 담을 수 있는 배낭의 최대 무게가 주어집니다.
• 이 때 베낭에 넣을 수 있는 물건들의 최대 가치를 구하는 문제입니다.
• 해당 냅색문제에서는 물건을 쪼갤 수 없다고 가정합니다.

해당 문제에서 물건의 개수가 N = 4개이고, 베낭의 최대 용량은 K = 7입니다.

	1번째 물건	2번째 물건	3번째 물건	4번째 물건
W(무게)	6	4	3	5
V(가치)	13	8	6	12

 

dp[i][j] = 첫 번째 물건부터 i번째 물건까지 살펴봤을 때, 베낭의 용량이 j인 경우 베낭에 있는 물건들의 가치의 최대값

즉 인덱스를 1부터 시작한다고 했을 때, dp[N][K]에 들어있는 값이 최대 가치입니다.

dp[i][j]를 계산해 나가는데 이 문제의 중점입니다. i번째에서 무게를 j까지 늘려가면서 베낭에 담을 수 있는 가치를 계산합니다.

• i번째 물건의 무게는 W[i]이고 가치는 V[i] 입니다.
• 해당 물건을 베낭에 넣을 때 판단할 수 있는 조건은 2가지입니다. 이 물건을 넣거나 넣지않거나.
  • 이 물건을 넣지 않았을 때의 최대값은 dp[i-1][j] 입니다. dp[i-1][j] 의 값은 베낭의 용량이 j 였고 i - 1번째 물건까지 살펴봤을 때의 최대 가치 합입니다.
  • 이 물건을 넣었을 때의 최대값은 dp[i-1][j - W[i]] + V[i] 입니다.  dp[i-1][j - w[i]]은 무게가 j인 가방에 i 번째의 물건의 무게 W[i]가 들어갈 수 있는 상황에서의 가치입니다. 거기에 현재 물건의 가치 V[i]를 더해주면 최대 가치 합을 구할 수 있습니다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

 

 

제출 코드

import sys
input = sys.stdin.readline

# 물건 개수, 최대 무게
n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]


data = [(0,0)]
for _ in range(n):
    # 무게, 가치
    w, v = map(int, input().split())
    data.append((w,v))


for i in range(1, n+1):
     weight, val = data[i][0], data[i][1]

     for j in range(1, k+1):
        if j < weight:
             dp[i][j] = dp[i-1][j]
            
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)

print(dp[n][k])