[Python] 냅색 알고리즘 (Knapsack Problem), 백준 12865. 평범한 배낭

🎒 Knapsack Problem

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

담을 수 있는 물건이 나누어 질 때

→ 분할가능 배낭문제 → 그리디 알고리즘으로 해결할 수 있음

담을 수 있는 물건이 나누어질 수 없을 때

→ 배낭 문제

---

🥇 평범한 배낭

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

---

📝 냅색 알고리즘을 활용한 풀이과정

먼저 주어진 예제를 활용하면 다음과 같이 표를 작성할 수 있다.

물품의 수는 총 4개, 버틸 수 있는 무게가 7이므로

다음과 같이 열이 7까지인 표를 만들어준다.

표의 각 칸에는 이전에 등장한 행들의 경우를 포함하여 얼마만큼의 가치를 담을 수 있는지 저장한다

무게 W / 가치 V 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	0	0
4 / 8	0	0	0	0	0	0	0	0
3 / 6	0	0	0	0	0	0	0	0
5 / 12	0	0	0	0	0	0	0	0

첫 번째 물건 6 / 13

무게 W / 가치 V 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	0	0	0	0
3 / 6	0	0	0	0	0	0	0	0
5 / 12	0	0	0	0	0	0	0	0

첫 번째 물건은 6kg 이므로 0부터 5kg 까지는 물건을 못담고, 6kg과 7kg 일 때 물건을 담을 수 있고 가치는 13이다

두 번째 물건 4 / 8

무게 W / 가치 V 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	0	0	0	0	0
5 / 12	0	0	0	0	0	0	0	0

두 번째 물건은 4kg 이므로 4 ~ 7kg일때 담을 수 있다.

그러나 6, 7kg 일 때는 13kg인 첫 번째 물건을 담는 게 더 가치가 높고, 둘다 담으면 무게를 초과하기 때문에 첫 번째 물건만 담는다.

세 번째 물건 3 / 6

무게 W / 가치 V 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	0	0	0	0	0

세 번쩨 물품은 3kg 일 때 6이므로 6을 저장하고,

나머지 4 ~ 6 kg 일때는 앞선 값이 더 크므로 이전의 값들을 저장한다.

이때 7kg일 경우에는 두 번째 물건과 세 번째 물건의 합이 7kg이고, 두 가치의 합 또한 14로 13보다 크기 때문에 갱신해 준다.

네 번째 물건 5 / 12

무게 W / 가치 V 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

네 번째 물품의 경우 5kg에 가치가 12이므로, 5kg 일때를 제외하고는 이전의 값들이 더 크다.

결과적으로 표의 가장 마지막에 담긴 14가 최댓값이 된다

💡 아이디어

위의 풀이를 바탕으로

물건의 종류 n과 최대용량 k가 주어지면

X 축에는 0 ~ K 까지, Y 축에는 0 ~ N 까지의 이중배열을 만들어주고

2중 for문 (i, j) 으로 각각의 행을 차례로 돌면서 다음과 같은 연산을 한다.

1. 현재 물건 w 이 해당열의 무게 j 보다 크면, 담을 수 없는 물건이므로 이전물건 i-1 의 현재무게 j를 넣어준다
2. 현재 물건 w 이 해당열의 무게 j보다 같거나 작다면, 담을 수 있는 물건이므로
   1. 이전물건 i-1 의 해당열의 무게 j 에 해당되는 값
   2. 이전물건 i -1 에서 (해당열의 무게 j - 넣고싶은 무게 w) + 현재 물건의 가치 v
   둘 중 더 큰 값을 DP[i][j]에 넣어주면 된다.

🧑🏻‍💻 풀이코드

n, k = map(int, input().split())
# 주어지는 무게를 저장하는 배열
things = [(0,0)]

for _ in range(n):
    w, v = map(int, input().split())
    things.append((w, v))

# 풀이한 표와 같은 양식의 2중 배열
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 = things[i]
        if w > j:
            dp[i][j] = dp[i-1][j]   
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)            
            
print(dp[n][k])