[백준/Python] 12865 평범한 배낭

문제 링크

12865번: 평범한 배낭

 

문제 풀이

• 해당 문제는 다이나믹 프로그래밍 중에서도 배낭 문제에 속한다. 이는 n번째의 물건을 각각 담을지 담지 않을지에 따라 최댓값이 결정된다.
• 먼저, 1~k까지의 무게를 담을 수 있는 가방이 있다고 가정한다. 첫 번째 물건만 고려하면, 무게가 6이므로, 6이전의 무게일 때는 물건을 담을 수 없으므로 각 가방의 최대 가치는 0이 된다. 6부터는 담을 수 있으므로 최대 가치는 13이 된다.
• 두 번째 물건도 고려하면, 무게가 4이므로 4 이전의 무게일 때는 가방의 최대 가치가 0이 되지만, 4부터는 4의 가치인 8이 된다. 이후 가방 무게가 6일 때는 무게가 6인 물건을 담았을 때의 최댓값(dp[i][j-1])과 무게가 4인 물건(V[i])을 담고 무게가 2인 물건(존재하지 않으므로 0)을 담았을 때의 최댓값(dp[i-1][j-W[i]])을 더한 값과 비교하여 더 큰 값이 최댓값이 된다. 
• 마지막 물건까지 반복 수행하면, 다음과 같은 점화식을 세울 수 있다.

# i는 가방 무게, j는 물건 순서, W[i]는 각 물건의 무게, V[i]는 각 물건의 가치
dp[i][j] = max(dp[i][j-1], dp[i-1][j-W[i]] + V[i]) if W[i] > k else dp[i-1][j]

 

 

전체 코드

import sys

n, k = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

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

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

print(dp[-1][-1])