BOJ 12865: 평범한 베낭 [Python 3]

'베낭 문제'라는 알고리즘이 있다.

문제의 예시를 그려봤다.

분홍색 하이라이트가 정답이 나온 Path이고, 하늘색이 들고갈 수 있었던 짐을 들고 갔을 때를 의미한다.

 

지금 위치하고 있는 '들 수 있는 무게'가 짐의 무게보다 크다면, 짐의 무게를 들 수 있다는 뜻이기 때문에,

전 예시에서 현 위치만큼 '들 수 있는 무게'와 새로운 짐을 더한 무게 중 더 가치가 큰 것을 고른다.

 

분홍색 화살표를 따라서 보자.

4라는 무게일 때, 무게 4, 가치 8인 물건을 들 수 있다.

그래서 전까지 4라는 무게에서 들었던 가치와, 새로운 물건을 들었을 때의 가치를 비교한다.

 

그래서 0과 8을 비교해서, 8이라는 값이 나오는 것이다.

 

또한, 8에서 14가 될 때는,

7이라는 무게일 때, 무게 3, 가치 6짜리 물건을 들 수 있다.

그래서 전까지 7이라는 무게에서 들었던 13과, 새로운 물건을 들었을 때의 가치인 6에 4라는 무게에서 들었던 8이라는 가치를 더해서, 14를 만든다.

13과 14를 비교해서, 14를 선택한다.

 

 

코드는 다음과 같다.

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
data=[[0,0]]
for i in range(1,n+1):
    data.append(list(map(int,input().split())))
dp=[[0]*(k+1) for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,k+1):
        if j>=data[i][0]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-data[i][0]]+data[i][1])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[n][k])

 

굉장히 이해하기 난해하기 때문에, 반복적으로 복습해야할 것 같다.