[Python/Baekjoon] B12865. 평범한 배낭

💬 문제

문제 난이도: 골드 5

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

문제 설명

입력으로 첫 줄에 물품의 수 N(1<=N<=100), 물품을 넣을 가방이 버틸 수 있는 무게 K(1<=K<=100000)이 주어진다.
그리고 다음 N개의 줄에 물건의 무게 W(1<=W<=100000)와 물건의 가치 V(0<=V<=1000)이 주어진다.
N, K, W, V는 모두 정수이다.
배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 출력한다.

❗️접근 방법

DP(dynamic programming) , 0-1 Knapsack problem

DP 테이블

dp[n][k]
: n번째 물건까지 사용하고 무게합이 k일 때 최대 가치합

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split(' '))
items = []
dp = [[0] * (K+1) for _ in range(N)]
for _ in range(N):
    items.append(list(map(int, input().split(' '))))

for k in range(K+1):
    if items[0][0] <= k:
        dp[0][k] = items[0][1]

for n in range(1, N):
    w, v = items[n]
    for k in range(1, K+1):
        if w > k:
            dp[n][k] = dp[n-1][k]
        else:
            dp[n][k] = max(dp[n-1][k], dp[n-1][k-w] + v)

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

유사한 문제
HackerRank - The Coin change
비슷한 점
1️⃣ n번째 물건을 가방에 넣을지 말지 == i번째 동전을 조합에 포함시킬지 안할지
2️⃣ 물건의 무게합이 k인지 == 동전의 합이 n인지
다른 점
B12865: 최대 가치 합
-> n번째 물건까지 사용했을 때, max(n번째 물건을 포함하는 경우의 가치, n번째 물건을 포함하지 않은 경우의 가치)
The Coin change: 가능한 조합의 개수
-> i번째 동전까지 사용했을 때, i번째 동전을 포함하는 조합의 개수 + i번째 동전을 포함하지 않는 조합의 개수