[Python] 백준 12865 : 평범한 배낭 (0/1 knapsack problem)

https://acmicpc.net/problem/12865

머리말

0/1 Knapsack 문제

DP로 유명한 문제이자 NP-hard 문제로 유명한 문제..

 

작년 알고리즘 수업시간 때 배웠던 부분이 기억이 잘 나지 않아 첨부하였다.

수업 노트

코드

n, k = map(int, input().split())

weights = [-1]
values = [-1]
for i in range(n):
    w, v = map(int, input().split())
    weights.append(w)
    values.append(v)

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

for i in range(1, n + 1):
    for w in range(1, k + 1):
        if weights[i] <= w:
            dp[i][w] = max(dp[i-1][w], values[i] + dp[i-1][w-weights[i]])
        else:
            dp[i][w] = dp[i-1][w]

print(dp[n][k])

더 읽을거리

• '코드없는 프로그래밍'님의 설명
• '코딩 공부 일지' 블로그의 해설