[백준 BOJ_12865] 평범한 배낭 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법을 이용하여 풀어주었습니다.

cache는 다음과 같습니다.

cache[i][j] = i번째 물건까지 고려했을 때, 최대 j 무게를 가지는 물건의 가치 최대 합

물건의 무게(W)와 가치(V)를 입력받고, 1부터 K까지 돌려주며

• j가 W보다 클 때
  • 고려해준 물건이 한 개일 경우는 그냥 그 물건의 가치를 저장합니다.
  • 그렇지 않을 경우에는 이전 물건까지의 가치 중, j-W 무게의 가치에서 현재 물건의 가치를 포함하는 값과 현재 물건을 포함하지 않는 경우를 비교하여 더 큰 값으로 저장해줍니다.
• j가 W보다 작을 때
  • 이전 물건까지의 가치 중 같은 무게의 값을 저장해줍니다.

마지막에는 cache[N][K]를 출력해줍니다.

코드

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
cache = [[0 for _ in range(K+1)] for _ in range(N+1)]
for i in range(1, N+1):
    W, V = map(int, input().split())
    for j in range(1, K+1):
        if j >= W:
            cache[i][j] = V if i == 1 else max(cache[i-1][j-W]+V, cache[i-1][j])
            continue
        cache[i][j] = cache[i-1][j]
print(cache[N][K])