백준 - 평범한 배낭 / Gold 5 / 12865번 / Python

문제 📋

백준 - 평범한 배낭

풀이 📝

import sys


def solution(n, k, stuffs):
    dp = [[0] * (k+1) for _ in range(n+1)]
    stuff = [(0, 0)]
    stuff.extend(stuffs)

    for i in range(1, n+1):
        weight, val = stuff[i]

        for j in range(1, k+1):
            if weight > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)
    return dp[n][k]


n, k = map(int, sys.stdin.readline().split())
stuffs = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

print(solution(n, k, stuffs))

유명한 문제인 0-1 Knapsack Problem이다.
DP배열을 정의하는데 어려움을 겪어서 풀이에 실패하여 다른 여러 풀이를 참고하였다.

먼저 2차원 DP배열은 다음과 같이 정의할 수 있다.

dp[i][j] : i번까지의 물건만 존재하고 무게가 j일 때의 최대 가치.

그리고 해당 dp 배열을 채워가면 답을 찾을 때는 다음과 같은 원칙을 따른다.

1. 만약 무게가 초과되어 담을 수 없다면 담지 않는다.

dp[i][j] = dp[i-1][j]

2. 만약 담을 수 있다면 담지 않는 것과 비교하면 이득이면 담는다.

dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + val)