[BOJ 12865] 평범한 배낭(Python)

문제

평범한 배낭

---

문제 해설

2차원 DP를 활용하는 아주 유명한 문제입니다. 0-1 knapsack 문제 라고도 하며, 분할 가능한 배낭 문제(Fractional Knapsack Problem)와 다르게 그리디 알고리즘으로 풀 수 없습니다.

D[i][j] = D[i - 1][j] ( 현재 보고있는 무게보다 넣으려는 아이템의 무게가 큼. )
D[i][j] = max( D[i - 1][j], D[i - 1][j - w] + v ) ( 현재 가방에 현재 아이템을 넣을 수 있음.)

점화식은 다음과 같습니다. 여기서 DP를 갱신하는 이유는 만약 물건을 넣을 수 있고, 물건을 넣었을 때 가치가 더 높은지를 확인하는 것입니다. 이것을 n 만큼 반복하면 구하고자 하는 K 무게에 가장 가치 있는 조합의 물건들만 들어가게 됩니다.

---

풀이 코드

n, k = map(int, input().split())
dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    item, value = map(int, input().split())
    for j in range(1, k + 1):
        if item > j:  # 현재 아이템의 무게가 현재 채우는 가방의 무게 보다 크면 덮어씀.
            dp[i][j] = dp[i - 1][j]
        else:
            # 현재 아이템을 넣을 수 있다면 전에 쓰던 아이템들과 비교를 해야함.
            # 전에 쓰던 아이템들을 그대로 가져갈 것이냐,
            # 아니면 현재 아이템을 넣어 가방의 무게를 맞출 것이냐
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item] + value)
print(dp[n][k])

---