[Python] Knapsack(배낭) 알고리즘

Knapsack Problem

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘

• Fractional Knapsack Problem
  물건을 쪼갤 수 있는 배낭 문제로, 가치가 높은 순으로 정렬한 뒤 배낭에 담고, 텍스트남은 부분은 물건을 쪼개어 넣어 조합을 찾을 수 있음. 그리디 알고리즘으로 해결 가능

• Knapsack Problem
  물건을 쪼갤 수 없는 배낭 문제로, 동적계획법(Dynamic Programming)을 활용해 해결 가능
  
  

---

Knapsack 문제 해결 과정

가방에 담을 물건 1~4가 아래와 같이 주어진다.

물건	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

가방에 넣을 수 있는 총 무게가 7kg이라고 할 때, 최대의 가치를 가지는 물건의 조합을 구하려고 한다.
이 때 knapsack 알고리즘을 활용해보자.

먼저, 2차원 테이블을 하나 만들어준다.

아래는 물건을 넣었을 때 무게 별 최대 가치를 나타내는 표이다.
여기서 행은 물건의 번호를 의미하고, 열은 가방에 넣을 수 있는 최대 무게,
그리고 표 내부의 칸은 해당 물건까지를 이용해 넣을 수 있는 최대 가치를 의미한다.

1) 물건을 넣지 않았을 때

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)
물건 2 (4kg)
물건 3 (3kg)
물건 4 (5kg)

위와 같이 물건을 넣지 않았을 때 가치는 0이다.

2) 물건 1만 넣을 수 있을 경우

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)
물건 3 (3kg)
물건 4 (5kg)

물건 1은 6kg이므로, 6kg 이후부터는 가치는 13이 채워진다.
단 이 단계에서는 물건 1만 넣을 수 있다고 가정하므로,
넣을 수 있는 무게가 7kg이 되어도 가치는 13으로 동일하다.

3) 물건 1~2를 넣을 수 있는 경우

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)
물건 4 (5kg)

가방에 넣을 수 있는 무게가 4kg이 되었을 때 부터 물건 2를 넣을 수 있다.
따라서 4kg일 때 가치는 8이 되고, 6kg일 때에는 물건 1도 넣을 수 있으므로,
물건 1~2중 가치가 더 큰 가치(13)를 채워준다.

4) 물건 1~3를 넣을 수 있는 경우

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)	0	0	0	6	8	8	13	14
물건 4 (5kg)

물건 3은 3kg이므로, 가방에 넣을 수 있는 무게가 3kg가 되었을 때부터 비로소 넣을 수 있다.
이 후부터는 위와 동일하나, 가방에 넣을 수 있는 무게가 7kg가 되었을 때,
물건 1의 가치(13)보다 물건 2+물건 3의 가치(8+6 = 14)가 더 크므로, 14를 채워준다.

5) 물건 1~4를 넣을 수 있는 경우

	0 kg	1 kg	2 kg	3 kg	4 kg	5 kg	6 kg	7 kg
X	0	0	0	0	0	0	0	0
물건 1 (6kg)	0	0	0	0	0	0	13	13
물건 2 (4kg)	0	0	0	0	8	8	13	13
물건 3 (3kg)	0	0	0	6	8	8	13	14
물건 4 (5kg)	0	0	0	6	8	12	13	14

물건 4는 5kg이므로, 가방에 넣을 수 있는 무게가 5kg일 때부터 넣을 수 있다.
이때 물건 4(12)의 가치가 물건 2(8)의 가치보다 크기 때문에 12을 채워준다.

위 과정을 점화식으로 표현하면 아래와 같다.

$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w_{i}]+v_{i}])$

$v_{i}$: 물건의 가치
$w_{i}$ : 물건의 무게
$dp[i][j]$ : 최대 이윤 ($i$ : 현재 넣은 물건의 번호, $j$: 넣을 수 있는 최대 무게)

이를 python 코드로 구현해보았다.

---

구현

n, k = map(int, input().split())
lst=[[0, 0]]
for _ in range(n):
    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 = lst[i][0]
        value = 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])

'''
입력
4 7
6 13
4 8
3 6
5 12

출력
14
'''