[백준] 12865번,python - 평범한 배낭(배낭 문제)

배낭 문제(KnapSack Problem) 그림으로 쉽게 이해하기

오래 고민하다가 위의 블로그 내용을 통해 풀이를 이해 하였다. 

https://www.acmicpc.net/problem/12865

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

for _ in range(n):
    v, w = map(int, input().split())
    items.append((w, v))

for i in range(1, n + 1):        # 물건
    v, w = items[i - 1]
    for j in range(1, k + 1):    # 무게
        if w > j:
            dp[i][j] = dp[i - 1][j]   # 이전 물건 그대로
        else:
            dp[i][j] = max(dp[i - 1][j],v + dp[i - 1][j - w]) # 선택 X, 선택 O

print(dp[n][k])   # 최대 가치