백준 12865 평범한 배낭 with Python

알고리즘

다이나믹 프로그래밍

Tip

다이나믹 프로그래밍(Dynamic Programming, DP)은 반복되는 부분 문제를 해결하기 위해 이전에 계산된 결과를 저장하고 재사용하는 알고리즘입니다. DP 문제는 다음과 같은 두 가지 특성을 가지고 있습니다.

Overlapping Subproblems: 하나의 큰 문제를 여러 개의 작은 문제로 나눌 수 있고, 작은 문제들이 서로 중복될 수 있습니다.
Optimal Substructure: 큰 문제의 최적 해는 작은 문제들의 최적 해로 구성됩니다.

DP 문제를 해결하기 위해서는 다음과 같은 단계를 거칩니다.

문제를 작은 부분 문제로 나눕니다. 부분 문제들의 최적 해를 계산합니다. 부분 문제들의 최적 해를 사용하여 전체 문제의 최적 해를 계산합니다. DP 문제를 해결하는 데는 크게 두 가지 방법이 있습니다.

Memoization : 재귀호출을 사용한 하향식 방법입니다. 메모이제이션 방식은 부분 문제의 최적 해를 저장하는 테이블을 사용합니다. 재귀호출을 사용하여 부분 문제를 해결할 때마다 테이블을 참조하여 이미 계산된 부분 문제의 최적 해를 사용합니다.
Tabulation : 상향식 방법입니다. 부분 문제의 최적 해를 계산하여 표로 표현하는 방법입니다. 부분 문제의 최적 해는 작은 부분 문제에서부터 큰 부분 문제로 순서대로 계산됩니다.

DP 문제를 해결하는 데는 다음과 같은 팁이 있습니다.

문제를 잘 분해하는 것이 중요합니다. 부분 문제가 잘 분해되면 전체 문제의 최적 해를 구하기가 쉬워집니다.
부분 문제의 최적 해를 계산하는 방법을 찾는 것이 중요합니다. 부분 문제의 최적 해를 계산할 수 없으면 DP를 적용할 수 없습니다.
memoization이나 tabulation을 적절하게 사용하는 것이 중요합니다. memoization이나 tabulation을 사용하면 DP 문제를 효율적으로 해결할 수 있습니다.

풀이 과정

1. 문제를 작은 부분 문제로 나누기

Idea: 각각의 물건은 선택되거나 선택되지 않는다.

물건의 개수가 i라고 가정할 때 물건들의 Set을 다음과 같이 표기할 수 있다.

S(i) → i번째 까지의 물건들의 Set = [ w[0], w[1], ..., w[i] ]

v[i] → w[i]의 가치

V(S(i), K) → 선택할 수 있는 물건의 종류가 1 ~ i이고 총 K 무게를 담을 수 있을 때 담을 수 있는 가치 V의 최댓값

이제 아래처럼 문제를 분할할 수 있다.

V(S(i), K) → max of V(Set(i-1), K - w[i]) + v[i] | V(Set(i-1), K) → i번째 물건을 선택하고 적재 용량 K를 물건의 가치 v[i]만큼 빼주거나 or 적재하지 않거나

2. Tabulation

V(S(i), K), 즉 물건의 인덱스(i)와 가치 k를 memorize한다.

물건의 개수 N을 행으로 놓고 가치 K를 열로 놓은 2차원 배열 dp를 생성한다.

dp[i][j] → 선택할 수 있는 물건의 종류가 ~i까지 있고 총 j 무게를 담을 수 있을 때 담을 수 있는 가치의 최댓값

전체 코드

import sys

input = sys.stdin.readline

N, K = map(int, input().split())

items = [[0, 0]]  # 무게, 가치
for _ in range(N):
    items.append(list(map(int, input().split())))

# dp[i][j] -> 물건의 종류가 ~i까지 있고 가방의 용량이 j개 있을 때 담을 수 있는 가치의 최댓값
dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(1, N + 1):  # 무게
    for j in range(1, K + 1):  # 가치
        w = items[i][0]
        v = items[i][1]

        if j < w:  # 물건의 용량이 최대 적재 용량을 초과한다면 뽑을 가능성 X, 따라서 set에서 제외시킨다.
            dp[i][j] = dp[i - 1][j]
        else:  # 물건을 뽑거나 뽑지 않거나
            dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j])

print(dp[N][K])