BOJ 12865번: 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

아이디어:

배낭 문제

dp[i][k] = 최대 배낭 수용 무게가 k일때, i번째 까지의 물건을 봤을 때 가치의 최대합

i번째 물건을 넣을 수 있는 경우(k>=wi): max(dp[i-1][k-wi]+vi, dp[i-1][k]) i번째 물건을 넣을 때 vs 넣지 않을 때 가치가 더 큰 것 선택

i번째 물건을 넣을 수 없는 경우(k<wi): dp[i-1][k] 이전 값이 그대로

-> dp[n][k] 출력

import sys
n, k = map(int, sys.stdin.readline().split())
arr = []
arr.append([0,0])

for _ in range(n):
    arr.append(list(map(int, sys.stdin.readline().split())))
dp = [[0]*(k+1) for _ in range(n+1)]

#dp[i][j] = 최대 배낭 수용 무게가 j일때, i번째 까지의 물건을 봤을 때 가치의 최대합
for i in range(1,n+1):
    for j in range(1, k+1):
        #i번째 물건을 넣을 수 있는 경우
        if (j>=arr[i][0]):
            #물건을 넣는 경우, 넣지 않는 경우 중 가치합이 더 큰 것 저장
            dp[i][j] = max(dp[i-1][j-arr[i][0]]+arr[i][1], dp[i-1][j])
        #i번째 물건을 넣을 수 없는 경우
        else:
            dp[i][j] = dp[i-1][j]
            
print(dp[n][k])