[골드 5] 백준 12865 - 평범한 배낭 (파이썬)

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

풀이

• 물건 개수 : N
• 배낭의 최대 무게 : K
• 각 물건은 W, V : 무게, 가치
• 각 물건은 한 번만 쓸 수 있다.

무게 ≤ K 조건을 만족하면서 가치의 합을 구하는게 목표

기본적인 다이나믹 프로그래밍인데 나는 왜이렇게 어렵게 느껴지는걸까.

먼저 dp[j]는 무게 j일때, 만들 수 있는 최대 가치를 나타낸다.

그래서 dp = [0] * (K+1)로 무게 0부터 K까지 모든 무게에 대해, 처음엔 가치를 0으로 초기화 한다.

dp = [0] * (K + 1)

점화식을 다음과 같이 구성한다.

for w, v in items :
    for j in range(K, w - 1, -1) :
        dp[j] = max(dp[j], dp[j - w] + v)

현재 배날 최대 무게가 j일때, 물건 (w, v)를 넣을 수 있다면

• 넣지 않은 경우 : dp[j]를 그대로 유지
• 넣은 경우 : dp[j - w] + v 이전에 무게 j - w였을때에 이 아이템을 넣어서 무게 j를 만드는 경우

왜 거꾸로 순회하는가?

• 한 아이템을 중복으로 선택하지 않기 위해서

예를 들어서 K = 10, 물건 = (2, 3)

for j in range(w, K + 1) :
	dp[j] = max(dp[j], dp[j - w] + v)

여기서 dp[j - w]는 이미 이 물건이 반영된 값일 수 있다.

그래서 한 물건을 여러번 넣는 무한배낭이 될 수 있기에, 뒤로 순회한다.

예를 들어서 다음과 같은 상태라면

N = 1
K = 5
item = (w=2, v=3)

초기 DP 배열은 다음과 같다.

dp = [0, 0, 0, 0, 0, 0]

• j = 5: dp[5] = max(0, dp[3] + 3) = 3
• j = 4: dp[4] = max(0, dp[2] + 3) = 3
• j = 3: dp[3] = max(0, dp[1] + 3) = 3
• j = 2: dp[2] = max(0, dp[0] + 3) = 3

dp = [0, 0, 3, 3, 3, 3]

코드

# 백준 12865 - 평범한 배낭
# 분류 : 다이나믹 프로그래밍
# 문제집 : 단기간 성장 - 1번

N, K = map(int, input().split())
items = [tuple(map(int, input().split())) for _ in range(N)]

dp = [0] * (K + 1)

for w, v in items :
    for j in range(K, w - 1, -1) :
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[K])