[BOJ-12865][C++] 평범한 배낭

문제

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

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

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

 

알고리즘 분류

• 다이나믹 프로그래밍
• 배낭 문제

 

문제 출처

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

---

 

문제 해결 방법

• 이 문제는 0-1 배낭 문제를 DP를 이용하여 푸는 문제이다.
  • 0-1 배낭 문제(0-1 Knapsack Problem) : 짐을 쪼갤 수 없는 경우 (DP 사용)
  • 분할 가능 배낭 문제(Fractional Knapsack Problem) : 짐을 쪼갤 수 있는 경우 (그리디 알고리즘 사용)
• 잘 알려진 0-1 배낭 문제의 점화식은 다음과 같으며, @DP[i][j]@는 @i@개까지의 물건을 넣는 경우에서 무게가 @j@일 때, 가치의 최댓값을 의미한다,
  • @i@ : 배낭에 넣을 물건 번호
  • @j@ : 현재 배낭의 무게

$$DP[i][j] = \begin{cases} \text{max}(DP[i - 1][j], \; DP[i - 1][j - W[i]] + V[i]) & \text{if  j ≥ W[i]} \\ DP[i - 1][j] & \text{if  j < W[i]} \end{cases}$$

• 이 점화식을 토대로 코드를 작성하면 다음과 같다.

int Knapsack01(int n, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1 ; j <= k; j++) {
            if (j >= W[i]) {    // 물건을 넣을 수 있는 경우
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
            }
            else {    // 물건을 넣을 수 없는 경우
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][k];
}

 

예제를 이용하여 알고리즘 작동 원리 이해하기

• @예제 입력 1@을 이용하여 알고리즘의 작동 원리를 이해해보자.
  • 물건의 수(@N@)는 @4@, 배낭에 넣을 수 있는 물건 무게의 최댓값(@K@)은 @7@로 주어졌다.
  • 그리고 각 물건의 무게(@W@)와 가치(@V@)가 다음과 같이 주어졌다.

	0	1	2	3	4
W	0	6	4	3	5
V	0	13	8	6	12

N \ K	0	1	2	3	4	5	6	7
0
1
2
3
4

 

① @N = 0@일 경우

• 배낭에 넣을 수 있는 물건의 수(@N@)는 @0@이다.

	0	1	2	3	4
W
V

• 배낭에 넣을 수 있는 물건이 없으므로, 모든 무게에서 가치는 0이다.

N \ K	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1
2
3
4

 

② @N = 1@일 경우

• 배낭에 넣을 수 있는 물건의 수(@N@)는 @1@이다.

	0	1	2	3	4
W	0	6
V	0	13

• 배낭에 물건을 1개만 넣는데, 배낭에는 @물건1@만 넣을 수 있다. 
• @물건1@의 무게(@W[1]@)는 6, 가치(@V[1]@)는 13이므로 @K ≥ 6@, 즉 @K = 6, 7@일 때의 값을 13으로 업데이트 해준다.
• 따라서 다음과 같이 표를 채울 수 있다.

N \ K	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2
3
4

 

③ @N = 2@일 경우 

• 배낭에 넣을 수 있는 물건의 수(@N@)는 @2@이다.

	0	1	2	3	4
W	0	6	4
V	0	13	8

• 배낭에 물건들을 넣는데. 넣을 수 있는 물건의 수는 2개이고, 배낭에 담긴 물건들의 가치가 최대가 되도록 해야한다.
• 기존에 넣었던 @물건1@이 아닌 @물건2@를 배낭에 넣어본다.
• @물건2@의 무게(@W[2]@)는 4, 가치(@V[2]@)는 8이므로 @K ≥ 4@, 즉 @K = 4, 5, 6, 7@일 때의 값을 8로 업데이트 해준다.
• 따라서 다음과 같이 표를 채울 수 있다.

N \ K	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	8	8
3
4

• 하지만, 앞에서 @물건1@을 배낭에 넣었을 때의 가치가 13이라는 것을 확인하였다. 
• @8 < 13@ 이므로, @K = 6, 7@일 때의 값을 더 큰 값인 13으로 갱신해준다.

N \ K	0	1	2	3	4	5	6	7
0	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

 

④ @N = 3@일 경우 

• 배낭에 넣을 수 있는 물건의 수(@N@)는 @3@이다.

	0	1	2	3	4
W	0	6	4	3
V	0	13	8	6

• 배낭에 물건들을 넣는데. 넣을 수 있는 물건의 수는 3개이고, 배낭에 담긴 물건들의 가치가 최대가 되도록 해야한다.
• 기존에 넣어봤던 @물건1@과 @물건2@가 아닌 @물건3@을 배낭에 넣어본다.
• @물건3@의 무게(@W[3]@)는 3, 가치(@V[3]@)는 6이므로 @K ≥ 3@, 즉 @K = 3, 4, 5, 6, 7@일 때의 값을 6로 업데이트 해준다.
• 따라서 다음과 같이 표를 채울 수 있다.

N \ K	0	1	2	3	4	5	6	7
0	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	6	6	6	6
4

• 하지만, 마찬가지로 @K ≥ 3@일 때, @V[3] = 6@의 크기가 이전의 가치들보다 작으므로, 다시 값을 더 큰 값으로 갱신해준다.

N \ K	0	1	2	3	4	5	6	7
0	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	13
4

• 배낭에 넣을 수 있는 물건들의 무게 합의 최댓값(@K@)은 7이다. 그러므로 @물건3@과 @물건2@를 함께 배낭에 넣을 수 있으며(@W[3] + W[2] = 3 + 4 = 7@), 이때의 가치의 합은 @V[3] + V[2] = 6 + 8 = 14@이다. @14@는 기존에 @K = 7@일 때의 가치(@13@)보다 더 크므로, @K = 7@일 때의 값을 14로 업데이트 해준다.
  • DP[3][7] = max(DP[3 - 1][7], DP[3 - 1][7 - W[3]] + V[3]) = max(DP[2][7], DP[2][7 - 3] + 6) = max(DP[2][7], DP[2][4] + 6) = max(13, 8 + 6) = max(13, 14) = 14

N \ K	0	1	2	3	4	5	6	7
0	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

 

⑤ @N = 4@일 경우 

• 배낭에 넣을 수 있는 물건의 수(@N@)는 @4@이다.

	0	1	2	3	4
W	0	6	4	3	5
V	0	13	8	6	12

• 배낭에 물건들을 넣는데. 넣을 수 있는 물건의 수는 5개이고, 배낭에 담긴 물건들의 가치가 최대가 되도록 해야한다.
• 기존에 넣어봤던 @물건1@과 @물건2@, @물건3@이 아닌 @물건4@를 배낭에 넣어본다.
• @물건4@의 무게(@W[4]@)는 5, 가치(@V[4]@)는 12이므로 @K ≥ 5@, 즉 @K = 5, 6, 7@일 때의 값을 12로 업데이트 해준다.
• 따라서 다음과 같이 표를 채울 수 있다.

N \ K	0	1	2	3	4	5	6	7
0	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	12	12

• 하지만, 마찬가지로 @K ≥ 6@일 때, @V[4] = 12@의 크기가 이전의 가치들보다 작으므로, 다시 값을 더 큰 값으로 갱신해준다.

N \ K	0	1	2	3	4	5	6	7
0	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

 

• 위의 설명을 코드로 표현하면 다음과 같다. 
  
  • @dp[i][j]@에서 @i@는 @N@, @j@는 @K@라고 생각하면 된다.

int Solution(int n, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1 ; j <= k; j++) {
            if (j >= W[i]) {    // 물건을 넣을 수 있는 경우
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
            }
            else {    // 물건을 넣을 수 없는 경우
                dp[i][j] = dp[i - 1][j];    // 그 전의 가치를 그대로 옮긴다.
            }
        }
    }
    return dp[n][k];
}

 

• 그림을 그려서 풀면 이해할 수 있었으나, 한 번에 이해하기가 너무 어려운 문제였다.

 

코드

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

int N, K;
int W[101];
int V[101];
int dp[101][100001];

void Input() {
    cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        cin >> W[i] >> V[i];
    }
}

int Solution(int n, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1 ; j <= k; j++) {
            if (j >= W[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][k];
}

void Output() {
    cout << Solution(N, K) << '\n';
}

void Solve() {
    Input();
    Output();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 골드V

 

배낭 문제(Knapsack Problem)

개념

• 조합 최적화 문제의 일종
• 담을 수 있는 최대 무게가 정해진 배낭과 함께 각각의 무게(W)와 가치(V)가 주어진 아이템의 집합이 주어졌을 때, 배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분 집합을 찾는 문제

 

분할 가능한 배낭 문제(Fractional Knapsack Problem)

• 가치(V)를 분할할 수 있는 배낭 문제
• 그리디 알고리즘(Greedy Algorithm)으로 풀 수 있다.

 

 

0-1 배낭 문제(0-1 Knapsack Problem)

• 가치(V)를 분할할 수 없는 배낭 문제
• 동적 계획법(DP) 또는 백트래킹(Backtracking)으로 풀 수 있다.

 

알고리즘

int Knapsack01(int n, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1 ; j <= k; j++) {
            if (j >= W[i]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - W[i]] + V[i]);
            }
            else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[n][k];
}

 

참고 사이트

• https://namu.wiki/w/%EB%B0%B0%EB%82%AD%20%EB%AC%B8%EC%A0%9C

배낭 문제 - 나무위키