[알고리즘] 냅색(knapsack) 알고리즘

배낭의 용량이 정해져 있을 때, 최대한의 가치를 가질 수 있도록 배낭을 싸야 하는 문제로 DP 알고리즘을 활용하는 문제 유형이다.

📌문제

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.
이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.
이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요?
각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

테스트 케이스
4 11
5 12
3 8
6 14
4 8
[출처] : 인프런 - 파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

📌풀이

2차원 배열을 활용할 수 있는데 이 때, 가로를 무게, 세로를 물건의 가치라고 둔다.

Ⅰ) 보석 가치 12의 무게 5kg을 선택하는 경우

0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	12	12	12	12	12	24	24

Ⅱ) 보석 가치 8의 무게 3kg를 선택하는 경우

0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	8	8	8	16	16	16	24	24	24

2차원 배열로 보면 아래와 같이 나타낼 수 있다.

0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	12	12	12	12	12	24	24
0	0	0	8	8	8	16	16	16	24	24	24

※ dp[i][j]라 함은 무게가 j이면서 i번째 물건까지를 선택해서 만들어 낼 수 있는 최대 가치라는 의미가 된다.

❓그렇다면 위의 2차원 배열은 어떻게 바뀌어야 할까?

0	1	2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	12	12	12	12	12	24	24
0	0	0	8	8	12	16	16	20	24	24	28

• dp[1][6] : 무게 5kg와 3kg의 보석을 가지고 만들 수 있는 최대 가치
  • dp[0][6] : 무게 5kg의 보석만으로 구성하는 경우(즉, 무게 3kg의 보석은 사용하지 않은 경우)
  • dp[1][6-3] + 8 : dp[1][3]은 현재까지 주어진 보석들로 무게 3kg일 때 최대 가치를 말한다. 이 때, 3을 빼는 이유는 3kg의 보석을 넣을 수 있는 공간을 만든다는 의미로 생각하면 이해가 쉽다.
  • 따라서, dp[0][6]은 무게 5kg인 보석을 이용해서 만들 수 있는 최대 가치 12와 무게 5kg, 3kg을 적절히 사용해서 만들 수 있는 최대 가치 16을 비교하여 16으로 갱신이 되는 것이다.
• dp[1][8] 역시 마찬가지다.
• dp[1][9] 역시 마찬가지다.

따라서, 이를 코드로 구현하면 아래와 같다.

import sys
input = sys.stdin.readline

N, limit = map(int, input().split())
items = [[0, 0]]

for i in range(N):
    weight, value = map(int, input().split())
    items.append((weight, value))

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

for i in range(1, N+1):
    for j in range(1, limit + 1):
        weight = items[i][0]
        value = items[i][1]
        if j < weight:
            dp[i][j] = dp[i-1][j]
        else:
            # 현재 보석을 선택하지 않는 경우의 최대 가치
            # 현재 보석을 선택한 경우의 최대 가치
            # 위의 두 가지 경우를 비교하여 더 큰 가치 선택
            dp[i][j] = max(dp[i-1][j], dp[i][j-weight] + value)
print(dp[N][limit])