[백준알고리즘] 12865번: 평범한 배낭 -Python

 

[백준알고리즘] 12865번: 평범한 배낭 -Python

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

12865번: 평범한 배낭

 

제목처럼 평범한 Dynamic Programming문제이다

 

처음에는 DFS와 upper bound를 이용한 Branch and Bound를 사용하려 하다가 사실상 Brute Force보다 조금 나은 수준의 코드가 되어버린 것 같았다... 실제로 시간초과도 뜸ㅠㅠ

 

BFS를 이용해서 사용하면 가능하지만, 이미 DFS로 피폐해져서 힙을 구성하기 힘들어서 DP로 풀었다.

(글을 쓰는 시점에서 heapq라는 min heap을 지원하는 모듈이 있다는 것을 알게 되었다.)

 

 

DP는 기본적으로 Optimal Solution을 구할 때 사용된다.

이때 Memoization을 사용하며 과정 중에 sub problems을 풀어나가게 된다. 즉, Recursion이 기본적인 아이디어이다.

하지만, 구현 시 무작정 재귀를 사용하는 것이 아닌 Overlapping sub problems를 Memoization 해두기 때문에 반복되는 일을 더 효과적으로 수행할 수 있다.

 

 

Kanpsack문제를 풀기 위해 일단 NxK행렬을 준비했다.

아이템/무게	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)
(3, 6)
(5, 12)

행별로 채워가면서 해당 무게별 채울 수 있는 가장 큰 값을 채워나가기 시작했으며 각 인덱스에는 해당 무게 때 가질 수 있는 최대의 가치가 들어가도록 했다.

일단 (6, 13)인 item만 가지고 각 무게를 채운다고 했을 때 5까지는 6의 무게가 나가는 item을 넣을 수 없기 때문에 0이며 6부터는 넣을 수 있으므로 13의 가치가 최대이다.

 

아이템/무게	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)	0	0	0	8	8	13	13
(3, 6)
(5, 12)

마찬가지로 진행하면서 3까지는 4의 무게를 갖는 item이 들어가지 못하기 때문에 0의 가치이고 4부터는 8의 가치를 갖는다. 하지만 이때는 (6, 13)과 (4, 8) 아이템 2개를 가지고 채우기 때문에 무게 6을 채울 때 가질 수 있는 최대 가치는 13이다.

 

한번 더 진행과정을 보이면 다음과 같다.

아이템/무게	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)	0	0	0	8	8	13	13
(3, 6)	0	0	6	8	8	13	14
(5, 12)

다음 표에서는 무게가 7일 때를 잘 봐야 한다. 아이템 (3, 6)을 포함시키지 않을 경우 (6, 13)만 들어간 13이 최대이겠지만, (3, 6)이 포함된다고 생각하면 (4, 8)과 같이 포함되어 14가 가장 높은 가치가 된다.

즉, 해당 인덱스에서 가장 높은 가치는 현재 고려하고 있는 아이템을 넣었을 때의 최댓값과 넣지 않았을 때의 최댓값을 비교해야 한다는 것이다.

 

따라서 i번째 아이템까지 주어진 후 j의 무게 안에서 구할 수 있는 최대 가치는 다음과 같다.

dp [i][j] = max(dp[i - 1][j], dp[i - 1][j - weight [i]] + value [i]]

dp [i - 1][j]: i번째 아이템을 챙기지 않았을 때의 최댓값

dp [i - 1][j - weight [i]] + value [i]]: i번째 아이템을 챙겼을 때 갖는 최댓값

(무게는 i번째 아이템을 포함해서 j가 되도록 하기 위해서 j에서 i의 무게를 뺀 값에서 i번째 아이템의 value를 더한다)

 

표를 완성한 모습은 다음과 같다.

아이템/무게	1	2	3	4	5	6	7
(6, 13)	0	0	0	0	0	13	13
(4, 8)	0	0	0	8	8	13	13
(3, 6)	0	0	6	8	8	13	14
(5, 12)	0	0	6	8	12	13	14

 

dp [i][j] = max(dp[i - 1][j], dp[i - 1][j - weight [i]] + value [i]])

식을 토대로 코드를 짜면 다음과 같다.

여기서는 (i - 1)과 (j - weight [i]) 때문에 위의 예시 표처럼 N x K Matrix가 아닌 (N+1) x (K+1) Matrix를 사용했다.

import sys

(N, K) = map(int, sys.stdin.readline().split())
item = [[0, 0]]
for i in range(1, N + 1):
    item.append(list(map(int, sys.stdin.readline().split())))
dp = [[0] * (K + 1) for _ in range(N + 1)]    # (N+1) x (K+1) matrix

for i in range(1, N + 1):
    for j in range(1, K + 1):
        if j >= item[i][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-item[i][0]] + item[i][1])
        else:                
            dp[i][j] = dp[i-1][j]

print(dp[N][K])

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다