[백준 12865] 평범한 배낭 (python)

12865번: 평범한 배낭

 

0/1 Kanpsack Problem -> DP로 푼다. 

1. [아이템, 가방허용치]를 뜻하는 arr 배열을 만든다.
2. 가방허용치가 아이템 무게보다 작다면, 이전 아이템의 가치(arr[i-1])를 가져온다.
3. 크거나 같다면, 이전 아이템의 가치와(arr[i-1]) 아이템과 허용치를 만들수 있는 가치(arr[i-1][j-w]) 중 큰값을 고른다.\
4. 마지막 값을 출력한다.

 

ex) 아이템 3(w)일때 허용치5(j) 이라면

• 1, 2 일때는 이전아이템(i-1)의 j를 가져온다.
• 3, 4, 5 일때는 이전아이템(i-1)의 허용치 j-w(5-3=2)인 것과 j인 것을 비교한다.

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
arr = [[0]*(K+1) for _ in range(N+1)]
items = [[]]

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

for i in range(1, N+1):
    w, v = items[i]
    for j in range(1, K+1):
        if j-w < 0:
            arr[i][j] = arr[i-1][j]
        else:
            arr[i][j] = max(arr[i-1][j], arr[i-1][j-w]+v)
        
            

print(arr[N][K])