BOJ 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)가 주어진다.

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

출력

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

재정의와 추상화

배낭 알고리즘 (Knapsack Algorithm)

배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 알고리즘을 뜻합니다.

이 문제는 대표적인 배낭 알고리즘 문제입니다. 문제에서 주어진 아래 예시를 가지고 설명하겠습니다.

4 7
6 13
4 8
3 6
5 12

총 물품의 수는 4개, 배낭에 담을 수 있는 무게의 최댓값은 7입니다. 아래는 4개의 물품을 설명의 편의를 위해 오름차순으로 정렬한 것입니다.

1. 무게 3, 가치 6
2. 무게 4, 가치 8
3. 무게 5, 가치 12
4. 무게 6, 가치 13

dp	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5	j = 6	j = 7
i = 0	0	0	0	0	0	0	0	0
i = 1	0	0	0	6	6	6	6	6
i = 2	0	0	0	6	8	8	8	14
i = 3	0	0	0	6	8	12	12	14
i = 4	0	0	0	6	8	12	13	14

* dp[i][j]는 j의 무게까지 담을 수 있는 배낭에 1번째부터 i번째 물품을 사용하여 배낭에 담을 수 있는 최대 가치를 뜻한다.
* obj[i]는 i번째 물품에 대한 정보를 뜻하고, obj[i].first는 그 물품의 무게, obj[i].second는 그 물품의 가치를 뜻한다.

3가지 예시를 통해 이해해보자.

• i = 2, j = 4 -> dp[2][4]
  1. obj[2].second == 8
     2번째 물품 하나를 가방에 넣으면 총 가치는 8, 총 무게는 4, 남는 무게는 0이다.
     이때, 1부터 1번째 물품을 사용해 남는 무게에 대한 가치 최댓값을 마저 더해주면 된다.
     --> obj[2].second + dp[2 - 1][4 - 4(obj[2].first)] == 8 + 0 == 8
  2. dp[2 - 1][4] == 6
     1번째부터 1번째 물품을 사용하여 총 무게를 4로 맞췄을 때 총 가치는 6
  3. 8 > 6이므로, dp[2][4] = obj[2].second + dp[1][0] == 8
• i = 2, j = 7 -> dp[2][7]
  1. obj[2].second == 8
     2번째 물품 하나를 가방에 넣으면 총 가치는 8, 총 무게는 4, 남는 무게는 3이다.
     이때, 1부터 1번째 물품을 사용해 남는 무게에 대한 가치 최댓값을 마저 더해주면 된다.
     --> obj[2].second + dp[2 - 1][7 - 4(obj[2].first)] == 8 + 6 == 14
  2. dp[2 - 1][7] == 6
     1번째부터 1번째 물품을 사용하여 총 무게를 7로 맞췄을 때 총 가치는 6
  3. 14 > 6이므로, dp[2][7] = obj[2].second + dp[1][7] == 14

단, 위 예시는 obj[i].first(i번째 물품의 무게)가 j 이하라는 것을 가정하였을 때 할 수 있는 이야기이다.

왜냐하면 j 이상이 아닐 경우, 남는 무게에 대한 dp[i - 1][j - obj[i].first]를 구할 때 j - obj[i].first가 음수가 되버리므로, 메모리 접근 오류가 발생하기 때문이다.

따라서, obj[i].first가 j 이하일 때만 위와 같은 매커니즘이 작동하도록 하고 dp[i][j]에 대한 기본값을 dp[i - 1][j]로 초기화 해놓으면 된다.

문제의 정답은 i = n, j = k일 때를 구하는 것이므로 답은 dp[n][k]이다.

점화식

// dp[i][j]의 초기값
dp[i][j] = dp[i - 1][j]
if (obj[i].first <= j) {
	dp[i][j] = max(obj[i].second + dp[i - 1][j - obj[i].second], dp[i][j])
}

코드 작성

#include <iostream>
#include <algorithm>
using namespace std;

pair<int, int> obj[101];
int arr[101][100001];

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> obj[i].first >> obj[i].second;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            arr[i][j] = arr[i - 1][j];
            if (obj[i].first <= j)
                arr[i][j] = max(obj[i].second + arr[i - 1][j - obj[i].first], arr[i][j]);
        }
    }
    cout << arr[n][k];
    return 0;
}