[Baekjoon] 12865. 평범한 배낭

문제 설명

문제

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

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

준서가 여행에 필요하다고 생각하는 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)가 주어진다.

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

출력

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

예제 입력 1

4 7
6 13
4 8
3 6
5 12

예제 출력 1

14

문제 풀이

# 다이나믹 프로그래밍 # 냅색

냅색 알고리즘은 분할 가능 냅색 문제와 0-1 냅색 문제(분할 불가 냅색 문제)로 나뉘는데, 이 문제의 경우 0-1 냅색 문제에 해당한다.

가방에 물건을 담다 보면, 두 가지 상황이 나온다.

첫째는 무게 때문에 가방에 현재 물건을 담을 수 없는 경우, 두번째는 담을 수 있는 경우이다.

물건을 담을 수 없는 경우에는 이전 것을 그대로 가져가면 된다. 하지만 담을 수 있는 경우에는 현재 물건을 담는 것이 더 가치있는지, 아니면 담지 않고 다른 물건을 담는 것이 더 가치있는지 알 수 없다.

바로 이 알고리즘을 짜준다.

우선 dp 배열을 생성한다. dp[n][k] = maxvalue를 만들어준다. 이는 n번째 물건까지 살펴보았을 때 무게가 k인 배낭의 최대 가치이다.

예를 들어 dp[2][3] = 7이면 2번째 물건까지 살펴봤을 때 무게가 3인 배낭의 최대 가치는 7이라는 것이다.

이 dp 배열을 이용하여 점화식을 작성한다.

앞에서 말했듯이, 물건을 담을 때의 상황은 두 가지로 나뉘고 이 중 물건을 담을 수 있는 경우가 중요하다.

1. 현재 물건을 담을 수 없는 경우: 현재 물건을 담지 않고 이전 배낭을 그대로 가져간다.
2. 현재 물건을 담을 수 있는 경우: 다음 두가지 경우 중 더 가치가 높은 배낭을 가져간다.
   • 2-1. 현재 물건을 배낭에 넣는다.
   • 2-2. 현재 물건을 배낭에 넣지 않고 그대로 가져간다.

위 과정을 식으로 나타내면 다음과 같다.

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

N, K = map(int, input().split())
items = [[0,0]] + [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]

for i in range(1,N+1): # 각 아이템
    for j in range(1,K+1): # 배낭의 무게
        w, v = items[i]
        if j < w: 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])

본인은 두번째 식인 dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])를 완전히 이해하는데 조금 애를 먹었는데, 앞에서 설명한 대로 따라가면,

i번째 물건까지 살펴봤을 때 무게 j인 배낭의 최대 가치는 i-1번째 아이템까지 살펴봤을 때 무게가 j-w 인 배낭에 무게가 w인 i번째 아이템을 넣었을 때의 배낭의 가치와 i-1번째 아이템까지 살펴봤을 때 무게 j를 갖는 배낭의 가치 중 큰 값이다.

와 같이 이해할 수 있다.

🔥 냅색 알고리즘 🔥은 동적 프로그래밍 문제 중 전형적인 문제이므로 알고리즘의 흐름을 잘 익혀두면 유용할 것이다.