[Python] 냅색 알고리즘(Knapsack Problem) - Dynamic Programming(DP)

냅색 알고리즘이란?

한 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제

 

냅색 알고리즘을 나누는 기준

담을 수 있는 물건이 나뉠 수 있는가, 없는가?

• 담을 수 있는 물건이 나누어 질 때
  • 분할가능 배낭문제(Fractional Knapsack Problem)
• 담을 수 있는 물건이 나누어질 수 없을 때
  • 0-1 배낭 문제(0-1 Knapsack Problem)

 

냅색 알고리즘 예시

가방에 20kg까지 담을 수 있습니다. 현재 3가지 물건을 가지고 있을 때, 가치를 최대로 가지려면 어떤 물건들을 담아야 하나요?

A : 가치 10, 무게 14kg
B : 가치 7, 무게 10kg
C : 가치 8, 무게 10kg

이 문제를 그리디 알고리즘으로 푼다면, 가치를 최대로 갖도록 최선의 선택을 하기 때문에 물건 A를 담고 끝날 것이다.

하지만, 정답은 B, C를 담는 것이다.

냅색 알고리즘의 핵심은, 특정 물건을 담지 않았을 때가 오히려 최선의 선택일 수 있음을 고려해주는 것이다.

 

DP를 이용한 냅색 알고리즘 풀이 방법

가방에 최대 N kg까지 담을 수 있을 때, dp[i][j]는 다음과 같다.

dp[i][j] = j개의 무게를 가방에 담을 수 있을 때, i개의 물건 중 담을 수 있는 최대 가치

 

1. j (현재 가방에 담을 수 있는 무게)가 현재 물건의 무게 w보다 작을 때
   • 현재 물건을 담을 수 없으므로, 이전 물건에서의 i에 해당하던 값(i-1)을 넣어준다.

$$ dp[i][j] = dp[i-1][j] $$

1. j가 현재 물건의 무게 w와 같거나 클 때
   • 현재 물건을 담을 수 있음
   • 물건을 담았을 때와 담지 않았을 때의 가치를 비교해준 뒤, 더 큰 값을 할당해줌
   • 현재 물건의 가치는 v

$$ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v) $$

물건의 최대 가치는 dp[가방 크기][물건의 개수]로 구할 수 있다.

 

대표 문제

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

12865번: 평범한 배낭

 

[평범한 배낭] 풀이 방법

1. i 는 n개 만큼의 물건의 개수, j 는 1 ~ k 까지의 무게이다.
2. 행을 돌면서 아래 알고리즘을 수행해보자.
   • 현재 물건이 현재 가방의 무게보다 작을 때
     • dp[이전 물건][같은 무게] 를 넣어준다.
   • 현재 물건이 현재 가방의 무게와 같거나 클 때
     • 현재 물건을 넣어주고, 남은 무게를 채울 수 있는 최대 값을 이전 물건 값에서 가져와 더해주거나, 현재 물건이 아닌 이전 물건으로 채우는 것 중에서 더 큰 값을 넣어준다. -> 현재까지의 물건들로 구성할 수 있는 가장 가치가 높은 구성
3. dp[n][k]는 무게가 K일 때, 최대의 가치를 넣을 수 있게 된다.

 

수식으로 표현하면 아래와 같다.

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

weight	value	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0	0
6	13	0	0	0	0	0	0	13	13
4	8	0	0	0	0	8	8	13	13
3	6	0	0	0	6	8	8	13	14
5	12	0	0	0	6	8	12	13	14

 

 

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
wv_lst = [[0, 0]]
for _ in range(n):
    wv_lst.append(list(map(int, input().split())))

dp = [[0] * (k+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, k+1):
        weight = wv_lst[i][0]
        value = wv_lst[i][1]

        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight] + value)

print(dp[n][k])