[DP] 백준 평범한 배낭 12865번 with Python3 ★

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

12865번: 평범한 배낭

 

문제

정답 풀이

import sys

N, K = map(int, input().split())
stuff = [[0,0]]


for _ in range(N):
    stuff.append(list(map(int, input().split())))


#냅색 문제 풀이
knapsack = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
#냅색에는 물건 가치가 원소로 저장된다. 

#i 물건 번호 / j 담을 수 있는 무게
for i in range(1, N + 1):
    for j in range(1, K + 1):

        #현재 i 번째 물건의 무게와 값
        weight = stuff[i][0] 
        value = stuff[i][1]

        #weight보다 현재 무게가 작으면(이 물건을 담을 수 없으면) 위의 값을 그대로 가져온다| 위의값= i-1 
        if j < weight:
            knapsack[i][j] = knapsack[i - 1][j] 

        #현재 물건 i를 담을 수 있으면. 
        else:
            knapsack[i][j] = max(value + knapsack[i - 1][j - weight], knapsack[i - 1][j])
        #value + knapsack[i - 1][j - weight] 
        # = 현재 물건의 값(value) 와 남은 무게(j-weight)에 저장된 최대 가치를 더한 값을 저장
        
        #knapsack[i - 1][j] 
        # 위의 경우(지금 물건 i를 담았을때)보다 
        # 이전 물건(i-1 혹은 그 이전 물건들)을 담았던 값이 더 클 경우도 있으니 비교.

print(knapsack[N][K])

출처:https://claude-u.tistory.com/208

 

해석

유명한 알고리즘인 냅색 알고리즘을 활용한 문제이다.

 

여러 경우를 고려해봤는데 아예 최대 무게를 제외한 이전단계부터 하나하나 계산하며 올라가는 식의 동적 프로그래밍은 떠오르지 않았다. 정말 DP는 너무 아이디어를 떠올리기 힘들다.