[Dynamic Programming] Knapsack 알고리즘

---

💡정의

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

Knapsack Problem은 크게 두 가지로 나뉩니다.

• 물건을 쪼갤 수 있는 Fraction Knapsack Problem
• 물건을 쪼갤 수 없는 0/1 Knapsack Problem

Fraction Knapsack Problem

물건을 쪼갤 수 있는 문제의 경우는 가치가 큰 물건부터 담고, 남은 무게 만큼 물건을 쪼개는 방식으로 Greedy Algorithm으로 해결이 가능합니다.

0/1 Knapsack Problem

물건을 쪼갤 수 없는 문제의 경우는 Dynamic Programming을 활용해 해결할 수 있습니다.

---

📝과정

Dynamic Programming을 활용해 0/1 Knapsack Problem을 해결하는 과정을 한 번 살펴보겠습니다.

문제

먼저, 가방에 담을 수 있는 물건의 무게와 가치가 아래 표와 같다고 가정하겠습니다.

물건	1	2	3	4
무게(kg)	6	4	3	5
가치(만원)	13	8	6	12

가방에 넣을 수 있는 총 무게가 7kg이라고 할 때, 최대의 가치를 가지는 물건의 조합을 구하려면 어떻게 해야할까요?

해결 방법

먼저, 2차원 테이블을 하나 만들어줍니다.
여기서 행은 물건의 번호, 열은 가방에 넣을 수 있는 최대 무게를 의미하고,
각 원소는 해당 물건을 이용해 넣을 수 있는 최대 가치를 의미합니다.

물건을 넣지 않았을 경우

	0kg	1kg	2kg	3kg	4kg	5kg	6kg	7kg
	0	0	0	0	0	0	0	0
물건 1
물건 2
물건 3
물건 4

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

물건 1을 넣을 수 있는 경우

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

물건 1은 6kg이므로, 6kg 이후부터 가치는 13이 됩니다.
단, 물건 1만 넣을 수 있으므로
넣을 수 있는 무게가 7kg이어도 가치는 13으로 동일합니다.

물건 1, 물건 2를 넣을 수 있는 경우

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

가방에 넣을 수 있는 무게가 4kg이 되면, 물건 2를 넣을 수 있습니다.
따라서 넣을 수 있는 무게가 4kg인 지점부터 가치는 8이 되고,
넣을 수 있는 무게가 6kg일 때부터는 물건 1도 넣을 수 있기 때문에,
더 큰 가치인 13이 채워지게 됩니다.

물건 1, 물건2, 물건3을 넣을 수 있는 경우

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

물건 3은 3kg이므로, 가방에 넣을 수 있는 무게가 3kg인 지점부터 넣을 수 있습니다.
이 후부터는 이전과 동일한 매커니즘으로 진행되나, 가방에 넣을 수 있는 무게가 7kg이 되었을 때, 물건 1의 가치인 13보다 물건 2와 물건 3을 같이 넣은 가치인 14가 더 크므로, 14가 채워지게 됩니다.

모든 물건을 넣을 수 있는 경우

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

물건 4는 5kg이므로, 가방에 넣을 수 있는 무게가 5kg일 때부터 넣을 수 있습니다.
이 때, 물건 4의 가치가 물건 2의 가치보다 크기 때문에 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$ : 넣을 수 있는 최대 무게)

---

💻구현

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])

---

📚Reference
배낭 문제(Knapsack Problem) - 테리의 일상