백준 / 12865번 / 평범한 배낭 / python 파이썬

 

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

 

 

DP 점화식을 세우는 것이 어려워서 최근에 DP 문제만 풀고 있는데 아직 접근법을 떠올리기 힘든 것 같다.

 

dp[i]는 배낭의 최대 용량이 i일 때 얻을 수 있는 최대 가치를 의미한다.

dp[i - w] + v 은 무게 w인 아이템을 추가하여 무게 i가 되었을 때 새로운 최대 가치를 계산하는 부분이다.

max(dp[i], dp[i - w] + v)를 계산해, 현재 아이템을 넣었을 때와 넣지 않았을 때 중 최대 가치를 선택해 dp[i]를 갱신한다.

 

예를 들어 배낭의 최대 용량이 7일 때, 무게와 가치가 각각 (3, 4), (4, 5), (2, 3)인 아이템들이 있다면

  1. dp 테이블을 dp = [0] * (K + 1) # [0, 0, 0, 0, 0, 0, 0, 0]와 같이 초기화 한다. 

  2. 각 아이템에 대해 dp 배열을 갱신한다. 

    1) 첫 번째 아이템 (무게 3, 가치 4)

      배낭 용량 i=7부터 i=3까지 계산, dp[i] = max(dp[i], dp[i - 3] + 4)의 점화식을 적용

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

갱신 후 dp = [0, 0, 0, 4, 4, 4, 4, 4]

 

 

    2) 두 번째 아이템 (무게 4, 가치 5)

      배낭 용량 i=7부터 i=4까지 계산, dp[i] = max(dp[i], dp[i - 4] + 5)의 점화식을 적용

 

• i=7: dp[7] = max(dp[7], dp[3] + 5) = max(4, 4 + 5) = 9
• i=6: dp[6] = max(dp[6], dp[2] + 5) = max(4, 0 + 5) = 5
• i=5: dp[5] = max(dp[5], dp[1] + 5) = max(4, 0 + 5) = 5
• i=4: dp[4] = max(dp[4], dp[0] + 5) = max(4, 0 + 5) = 5

갱신 후 dp = [0, 0, 0, 4, 5, 5, 5, 9]

 

이와 같이 진행하면 배낭의 최대 용량을 넘지 않고 담을 수 있는 최대 가치를 찾을 수 있다.

 

 

---

 

정답

N, K = map(int, input().split())
dp = [0] * (K + 1)

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(K, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)
print(dp[K])