[백준/Python] 12865_평범한 배낭

문제

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

12865번: 평범한 배낭

풀이

DP를 이용합니다.

문제의 예제를 dp table에 나타내면 아래와 같습니다.

물품 \ 가치 합	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)	0	0	0	8	8	13	13
(3, 6)	0	0	6	8	8	13	14
(5, 12)	0	0	6	8	12	13	14

입력받은 물품들을 (weight, value)형태로 stuff 리스트에 저장합니다.

(n + 1) * (k + 1) 크기의 2차원 배열 dp를 선언하고 0으로 초기화합니다.

dp를 이중 for문으로 순회하면서 i >= stuff[i][0]일 때, dp[i-1][j]와 (dp[i-1][j-stuff[i][0]] + stuff[i][1]) 중 큰 수를 dp에 저장합니다.

그 외 경우에는 dp[i-1][j]를 저장합니다.

dp의 최대값이 배낭에 넣을 수 있는 가치합의 최대값이 됩니다.

코드

import sys


n, k = map(int, sys.stdin.readline().rstrip().split())
stuff = [(0, 0)]
for _ in range(1, n + 1):
    w, v = map(int, sys.stdin.readline().rstrip().split())
    stuff.append((w, v))
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 >= stuff[i][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stuff[i][0]] + stuff[i][1])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[-1][-1])