[백준][Python] 12865번 평범한 배낭 - 코팩

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

풀이

배낭 알고리즘이라 불리는 다이내믹 프로그래밍 알고리즘의 일종.

1행과 1열의 원소값들은 0값으로 고정해준다.

행은 배낭의 무게를 뜻하고, 열은 물건의 번호를 뜻한다.

 

i번째 물건을 가방 안에 넣을 수 없는 경우 -> 이전까지 최댓값을 저장해준다.

i번째 물건을 가방 안에 넣을 수 있다면 -> dp에서 i번째 물건과 같이 넣을 수 있는 최대 가치와 합한 값과 이전 까지 j 무게에서 넣을 수 있는 물건의 최대가치와 비교해서 최댓값을 저장해준다.

 

코드

# 12865번 평범한 배낭
import sys
n, k = map(int, input().split())
dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    w, v = map(int, sys.stdin.readline().split())
    for j in range(1, k+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
print(dp[n][k])

 

출력결과