#26 [파이썬] 백준 12865번: 평범한 배낭

<문제>

https://www.acmicpc.net/

Baekjoon Online Judge

---

 

<소스코드>

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
D = [[0]*(K+1) for _ in range(N+1)]
W = []
V = []

for _ in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)

for i in range(1, N+1):
    for j in range(1, K+1):
        if j < W[i-1]:
            D[i][j] = D[i-1][j]
        else:
            D[i][j] = max(D[i-1][j], D[i-1][j - W[i-1]] + V[i-1])

print(D[N][K])

---

 

<NOTE>

· 물건의 총 개수 : N = 4

· 배낭의 최대 무게: K = 7

· 물건의 무게와 물건의 가치: W, V

(6, 13)

(4, 8)

(3, 6)

(5, 12)

 

위의 정보가 주어졌을 때, 물건의 인덱스가 행이고 무게의 구분이 열인 matrix를 만든다. matrix의 값으로는 무게가 j이하인 것 중에서 i번째 물건까지 고려했을 때 최대의 가치를 갖는 물건의 가치 V를 적는다. 최대의 가치인지를 판별하는 식은 아래와 같다. 

 

 

	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5	j = 6	j = 7
i = 0	0	0	0	0	0	0	0	0
i = 1	0	0	0	0	0	0	13	13
i = 2	0	0	0	0	8	8	13	13
i = 3	0	0	0	6	8	8	13	14
i = 4	0	0	0	6	8	12	13	14

 

이렇게 채우면 각 무게 j가 1씩 올라갈 때마다 첫번째 물건까지 고려했을 때, 두번째 물건까지 고려했을 때, 세번째 물건까지 고려했을 때, 네번째 물건까지 고려했을 때를 탐색하여 최대 가치를 갖는 물건을 고를 수 있다. i - 1까지의 물건을 고려하면서 무게 j에서 i번째 물건의 무게를 빼고 남은 무게의 최대 가치와 넣을 지 말 지 판단 중인 i번째 물건의 가치를 더한 값과 이전까지 최대 가치로 판단된 값을 비교하여 더 큰 가치를 가지는 물건의 가치를 넣는다.