[백준(BOJ)] #12865- 평범한 배낭 (파이썬, PyPy3)

문제

 

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

12865번: 평범한 배낭

 

---

문제 풀이

 

이 문제는 대표적인 냅색 문제(Knapsack Problem)입니다. 냅색 문제는 배낭 문제라고도 불리며 동적 계획법을 사용해 푸는 문제 중 유명한 유형의 문제입니다.

 

2022.07.22 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

[파이썬으로 배우는 알고리즘] 동적 계획법(Dynamic Programming)

 

# 해당 물건을 넣을 수 있는 무게가 아니면
if j < W:
    # 이전 행의 값을 저장
    dp[i][j] = dp[i-1][j]
# 해당 물건을 넣을 수 있는 무게라면
else:
    # 이전 행에서 해당 무게를 뺀 인덱스 즉, (해당 물건을 넣기전의 무게 +
    # 해당 물건의 무게를 더한 값)과 해당 물건을 넣지 않은 무게를 비교해
    # 큰 값으로 갱신
    dp[i][j] = max(V + dp[i-1][j-W], dp[i-1][j])

 

풀이 과정을 보면서 자세히 알아보겠습니다.

 

풀이 과정

1) 각 물건들의 무게와 가치는 위와 같습니다. 

 

2) dp 테이블을 준비합니다. dp 테이블은 2차원 리스트이고 dp[i][j]가 의미하는 것은 i번 째 물건까지 고려하고 허용 용량이 j일 때의 최대 가치를 의미합니다.

 

3) 먼저 무게가 6이고, 가치가 13인 물건을 고려합니다. 허용 용량이 6일 때부터 해당 물건을 저장할 수 있습니다. 허용 용량이 6일 때 이전 행, 같은 허용 용량에서 가치의 값(처음이므로 0)과 비교하여 큰 값으로 갱신합니다. 해당 물건의 가치 13이 0보다 크므로 13으로 갱신합니다. j가 7일 때도 마찬가지로 13으로 갱신해줍니다.

 

4) 다음은 무게가 4고, 가치가 8인 물건을 고려합니다. 허용 용량이 4일 때부터 해당 물건을 저장할 수 있습니다. 허용 용량이 4일 때 이전 행, 같은 허용 용량에서 가치의 값(0)과 비교하여 큰 값으로 갱신합니다. 해당 물건의 가치 8이 0보다 크므로 8로 갱신합니다. j가 5일 때도 마찬가지로 갱신합니다. 허용 용량이 6일 때는 이전 행, 같은 허용 용량에서 가치의 값 13이 해당 물건의 무게보다 크기 때문에 해당 값으로 갱신합니다. j가 7일 때도 마찬가지로 갱신합니다.

 

5) 다음은 무게가 3이고, 가치가 6인 물건을 고려합니다. 허용 용량이 3일 때부터 해당 물건을 저장할 수 있습니다. j가 6일 때까지 위에 했던 작업과 똑같이 비교하여 갱신합니다. 하지만 j가 7일 때를 주의해야 합니다. 

 

이전 행, 같은 허용 용량 7에서 해당 물건의 무게 값 3을 뺀 허용 용량 4 즉, 이전 물건을 고려했을 때 가방에서 현재 물건을 제외한 허용 용량 4(7-3) 일 때의 최대 가치가 8입니다. 현재 물건의 무게는 3이고 해당 물건의 가치는 6이기 때문에 이 물건을 담는 다면 현재 허용 용량 7에서의 가치는 14가 됩니다. 만약 해당 물건을 담지 않으면 그냥 이전 행, 같은 허용 용량에서의 값 13이 그 가치가 됩니다. 따라서 이 두 경우를 비교해 큰 값으로 가치를 갱신해야 합니다.

 

max(해당 물건 담았을 때의 최대 가치(해당 물건을 담기 전의 최대 가치 + 해당 물건의 무게), 해당 물건을 담지 않았을 때의 최대 가치) 

 

(지금까지 다른 값도 다 그렇게 계산한 것입니다. 하지만 해당 물건의 무게 값을 뺀 j에 있는 가치가 0이기 때문에 이전 행의 같은 무게에 있는 값이 가치로 갱신되었고 해당 과정에 대한 설명은 생략한 것입니다.)

 

6) 다음은 무게가 5이고, 가치가 12인 물건을 고려합니다. 허용 용량이 5일 때부터 해당 물건을 저장할 수 있습니다. 허용 용량이 5일 때 해당 물건의 가치 12가 이전 행, 같은 허용 용량 5에서의 값 8보다 크므로 12로 갱신합니다. 나머지도 똑같이 적용시킵니다.

 

---

구현

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
a.insert(0, [0,0])

dp = [[0] * (K+1) for _ in range(N+1)]

for i in range(1, N + 1):
    for j in range(1, K + 1):
        W, V = a[i]
        # 해당 물건을 넣을 수 있는 무게가 아니면
        if j < W:
        # 이전 행의 값을 저장
            dp[i][j] = dp[i-1][j]
        # 해당 물건을 넣을 수 있는 무게라면
        else:
            # 이전 행에서 해당 무게를 뺀 인덱스 즉, (해당 물건을 넣기전의 무게 +
            # 해당 물건의 무게를 더한 값)과 해당 물건을 넣지 않은 무게를 비교해
            # 큰 값으로 갱신
            dp[i][j] = max(V + dp[i-1][j-W], dp[i-1][j])
print(dp[N][K])

결과

 

더욱 효율적인 냅색 문제 풀이

위에서는 2차원 리스트의 dp 테이블을 사용하여 앞에서부터 순서대로 비교하면서 값을 갱신했습니다. 하지만 1차원 리스트의 dp 테이블로 마지막 인덱스부터 역순서로 비교하면서 dp 테이블을 갱신해 보다 더 적은 메모리로 빠른 시간 안에 풀 수 있는 방법도 있습니다.

 

코드

import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N, K = map(int, input().split())
    dp = [0] * (K+1)
    for _ in range(N):
        W, V = map(int, input().split())
        # 마지막 인덱스부터 해당 물건의 무게까지의 인덱스 까지 역으로 갱신
        for i in range(K, W-1, -1):
            # 현재 무게에서 최대 가치와 해당 물건의 무게를 뺀 무게에서 해당 물건의 가치를
            # 더한 값과 비교 즉, 해당 물건을 포함하여 더 큰 가치를 갖는지 확인하여 갱신
            dp[i] = max(dp[i], dp[i-W] + V)
    print(dp[K])

결과