[백준] 12865번 평범한 배낭

문제

무게 제한이 있는 가방에 여러개의 물건들을 넣었을 때 최대의 가치를 얻을 때 그 값을 구해라.
n개의 물건, 가방의 수용량은 k일 때 물건들은 w, v (무게, 가치) 순으로 주어진다.

ex)

n k
4 7
w v
6 13
4 8
3 6
5 12

풀이

가장 먼저 생각나는 방법은 브루트포스이다. 각 물건들의 유무를 따져가며 가방에 넣고 최대의 가치를 구하면 된다.
하지만 이 방법은 $2^n$으로 n은 최대 100을 가지기 때문에 $2^{100}$으로 $10^{30}$이다.
다른 방법을 생각해야 한다.

각 물건은 포함될수도 아닐수도 있다. 위의 ex)를 살펴보자. 4개의 물건을 A, B, C, D라 하겠다.
4개의 물건을 전부 살펴봤을 때 수용량 k인 가방안에 넣을 수 있는 최대가치를 f(ABCD, k)라 해보자.
f(ABCD, k) 값을 알고 있다고 할 때, 아직 D라는 물건을 살펴보지 않은 상태의 최대가치를 알 수 있을까?
f(ABCD, k) 상태에 D라는 물건이 포함되어 있다면 f(ABC, k - D무게) 포함되어 있지 않
다면 f(ABC, k)가 될 것이다.

자 그럼 다음과 같이 정리 할 수 있다.
dp[i][j]를 i번째 물건까지 살펴봤을 때 j가방에 넣을 수 있는 최대가치라 하자.

1. 1번부터 n번째 물건까지 살펴본다.
2. 현재 물건을 가방에 넣을 수 있을 때 ( $j >= w$ )
   dp[i - 1][j - w] + v
3. 현재 물건을 가방에 넣지 못할 때 ( $j < w$ )
   dp[i - 1][j]

전체코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
# 조건을 편하게 하기 위해 itemList와 dp에 dummy를 넣어둠
itemList = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)]

# 0은 dummy, 1부터 시작
for i in range(1, n + 1):
    w, v = itemList[i]

    for j in range(1, k + 1):
        dp[i][j] = dp[i - 1][j]
	
        if j - w >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)

print(dp[-1][-1])