[12865번] 평범한 배낭

백준 12865번 평범한 배낭

코드 풀이

• 예를 들어, dp[3][6] 의 값을 구하는 상황일 때를 가정해 보겠습니다.

• 용량이 6인 배낭에 i=3번째 물건을 넣지 않았을 때의 최대값은 dp[2][6] 에 저장되어 있습니다.

• 용량이 6인 배낭에 i=3번째 물건을 넣었을 때의 값은 dp[2][6-w[3]]+v[3]=dp[2][3]+v[3] 입니다.
  - 즉 i=3번째 물건을 넣고 용량이 6이 되었다는 말은 6-w[3] 크기의 가방에 w[3]을 더했다는 말과 같습니다.따라서 6-w[3] 크기의 가치합인 dp[2][6-w[3]]에 현재 i=3번째 물건을 넣었을 때의 가치인 v[3]을 더한 값이 됩니다.

• 둘 중 최대값이 바로 i번째 물건까지 넣는 것을 고려했을 때, 크기가 j인 가방에 넣을 수 있는 가치의 최대값입니다.

import sys

n, k = map(int, sys.stdin.readline().split(' '))

# 0행, 0열까지 추가하여 총 (n+1, k+1)
dp = [[0] * (k+1) for _ in range(n+1)]

w = [0]   # 무게
v = [0]   # 가치
for _ in range(n):
    x, y = map(int, sys.stdin.readline().split(' '))
    w.append(x)
    v.append(y)

# 냅색 알고리즘
# i: i번째 물건, j: 가방 총 용량이 j일 때
for i in range(1, n+1):
    for j in range(1, k+1):
    	# 현재 i번째 물건의 무게 w[i]가 가방 총 용량 j 이하라서 가방에 들어간다면,
        if j >= w[i]:
        	# 그 물건을 가방에 넣지 않았을 때의 가치합(dp[i-1][j])과 그 물건을 가방에 넣었을 때의 가치 총합(dp[i-1][j-w[i]]+v[i]) 중 최대값이 현재 i번째 물건을 j 크기 가방에 넣었을 때 최대 가치합.
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j] = dp[i-1][j]


print(dp[n][k])   # n개의 물건을 k 크기 가방에 넣는 것을 고려했을 때 최대 가치합

참고 자료:

• https://chanhuiseok.github.io/posts/improve-6/