[백준] 12865 : 평범한 배낭 - Python

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

import sys

N, K = map(int, sys.stdin.readline().split())
s = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
s.insert(0, [0, 0])
dp = [[0] * (K + 1) for _ in range(N+1)]

for i in range(1, N+1):
  for j in range(1, K+1): # j = 목표 무게
    if j < s[i][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(s[i][1] + dp[i-1][j-s[i][0]], dp[i-1][j])

print(dp[N][K])

 

1. 현재 물건의 무게가 목표 무게보다 작은 경우 : 이전 행의 가치 그대로 가져오기

2. 아닌 경우 :  '이전 행의 가치'와 '목표 무게에서 현재 물건을 넣었을 때, 남는 무게의 최대 가치' 중 최댓값

         - 목표 무게에서 현재 물건을 넣었을 때, 남는 무게의 최대 가치 = dp[i-1][j-s[i][0]]

	0	1	2	3	4	5	6	7
0, 0	0	0	0	0	0	0	0	0
6, 13	0	0	0	0	0	0	13	13
4, 8	0	0	0	0	8	8	13	13
3, 6	0	0	0	6	8	8	13	14
5, 12	0	0	0	6	8	12	13	14

ex) dp[3][7]은

13(이전 행의 가치)과 6+8(현재 물건의 가치 + 현재 물건을 넣었을 때 남는 무게의 최대 가치 : dp[2][7-3]) 중 최댓값인 14이다.