[TIL/크래프톤 정글9기] 30일차(백준 평범한 배낭 / DP)

오늘의 백준 문제는 평범한 배낭이다. DP를 활용하여 풀 수 있고 문제를 풀면서 DP테이블을 그려봐도 느낌적으로는 알겠는데, 정확히 왜 저런 점화식이 나오는지 이해가 가지 않았다.

아이패드가 없는 자의 서러움 너무 볼품이 없어 마크다운으로 DP테이블을 정리했다.

아이템↓\무게→	0	1	2	3	4	5	6	7
(0) 없음	0	0	0	0	0	0	0	0
(1) 6,13	0	0	0	0	0	0	13	13
(2) 4,8	0	0	0	0	8	8	13	13
(3) 3,6	0	0	0	6	8	8	14	14
(4) 5,12	0	0	0	6	8	12	14	14

행 1: 아이템 1 (무게 6, 가치 13)을 고려한 후: 무게 6 이상에서 13이 가능
행 2: 아이템 2까지 고려하면 무게 4에서 8, 무게 6에서는 여전히 아이템 1이 더 유리하므로 그대로 유지
행 3: 아이템 3을 더해 무게 6일 때, 3번(3,6) + 2번(4,8) = 14로 갱신
행 4: 아이템 4를 더해도 최대 가치는 여전히 14

이렇게 표로 DP테이블을 그려보면 점화식이 왜 저렇게 나온지 알 수 있다.

dp = [[0] * (k+1) for _ in range(n+1)]

• dp[i][j]는 "i번째 물건까지 고려하고, 무게 한도가 j일 때 얻을 수 있는 최대 가치"를 의미
• i: 0~n까지 (0은 물건 없음)
• j: 0~k까지 (0은 배낭 용량 0)

if j < w:
    dp[i][j] = dp[i-1][j]

• 현재 배낭 용량 j가 현재 물건의 무게 w보다 작으면, 이 물건은 배낭에 넣지 못함
• 따라서 이전 물건(i-1)까지 고려했을 때의 최적값(dp[i-1][j])을 그대로 유지

else:
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

현재 물건을 넣을 수 있을 때 두 가지 선택이 있음

• 1. 안 넣고 넘어간다 → dp[i-1][j]
• 2. 넣는다 → dp[i-1][j - w] + v
  • (남은 무게 j - w 에 대해 이전 단계에서 최대 가치 + 지금 물건의 가치 v)
• 둘중 가치가 큰 max값을 저장

정답 코드

# 평범한 배낭 문제 (Knapsack Problem) - 동적 계획법으로 해결
import sys
input = sys.stdin.readline

def dynamic(goods):
    dp = [[0] * (k+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, k+1):
            w = goods[i-1][0]  # 현재 물건의 무게
            v = goods[i-1][1]  # 현재 물건의 가치

            # 현재 물건의 무게가 배낭 용량보다 크면
            if j < w:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
    print(dp[n][k])
        
# 물건 개수, 최대 무게
n, k = map(int, input().split())
#무게, 가치
goods = [list(map(int, input().split())) for _ in range(n)]

dynamic(goods)