[BOJ / C++] 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)가 주어진다.

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

출력

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

Solved.ac 레벨

골드 V

풀이

배낭 문제라는 알고리즘이 있는 것 같다. 이 알고리즘에 대한 문제는 처음 접해보았고, 이 문제를 시작으로 차차 배낭 문제라는 알고리즘에 대해 이해를 해 나가면 될 것 같다.

따라서 이번 풀이는 나 스스로의 온전한 풀이가 아닌 많은 분들의 풀이 과정을 참고하며, 수기로 규칙을 찾고 점화식을 세워 문제를 풀어보았다.

 

아직 갈 길이 멀다.

 

예제를 기준으로 문제를 풀어보자.

n = 4 (물품의 갯수)

k = 7 (배낭에 담을 수 있는 무게 한도)

 

물품 4개를 vector<pair<int, int>> 타입으로 받았다.

first : 물품의 무게 / second : 물품의 가치

 

vector<pair<int, int>> wv (weight, value)

물품 / 물품 번호	1	2	3	4
first : 물품의 무게	6	4	3	5
second : 물품 가치	13	8	6	12

 

그리고 i = 물품 인덱스, j = 담을 수 있는 물건의 무게 한도로 하여 표의 빈칸을 채워나가보자.

표는 dp[i][j]를 나타내며, 이는 i개의 물건, j kg을 담았을 때 가질 수 있는 최대 가치를 나타낸다.

dp[n][k] 배열은 0으로 초기화 되어 있으며, 편의상 1 <= n, 1 <= k로 인덱싱한다.

i : 1 ~ 4

j : 1 ~ 7

 

편의상 Kg 단위를 붙였다.

 

1. 담을 수 있는 무게 한도가 1kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0
2 (4kg, 8)	0
3 (3kg, 6)	0
4 (5kg, 12)	0

주어진 물품 중 1kg인 물품은 없으므로 가치는 0 (dp[0][1] //아무것도 담지 않으며 한도가 1kg인 경우로 대체)

(dp 배열의 초기값은 0)

 

2. 담을 수 있는 무게 한도가 2kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0
2 (4kg, 8)	0	0
3 (3kg, 6)	0	0
4 (5kg, 12)	0	0

역시 주어진 물품 중 2kg인 물품은 없으므로 가치는 0

 

3. 담을 수 있는 무게 한도가 3kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0	0
2 (4kg, 8)	0	0	0
3 (3kg, 6)	0	0	6
4 (5kg, 12)	0	0	6

3번째 물품이 3kg, 가치를 6을 갖는다. 따라서 dp[3][3] (3번째 물품을 담으면서 한도가 3kg인 경우)에 해당 물품의 가치인 6을 적는다.

4번째 물품의 경우 5kg이라 3kg 한도의 배낭에 담을 수 없으므로, 최대값은 직전 값을 담는다.

 

4. 담을 수 있는 무게 한도가 4kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0	0	0
2 (4kg, 8)	0	0	0	8
3 (3kg, 6)	0	0	6	8
4 (5kg, 12)	0	0	6	8

2번째 물품이 4kg, 가치 8을 갖는다. 따라서 한 dp[2][4]에 해당 물품의 가치인 8을 적는다.

한도 4kg을 가득 채웠고, 이후 3kg, 6 가치의 물건을 담는 경우보다 4Kg, 8가치의 물건을 담는 편이 더 큰 가치를 갖기 때문에 8을 그대로 내려 적는다.

4번째 물품은 5kg이라 4kg 한도의 배낭에 담을 수 없으므로, 직전 값이 최대값이다.

 

5. 담을 수 있는 무게 한도가 5kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0	0	0	0
2 (4kg, 8)	0	0	0	8	8
3 (3kg, 6)	0	0	6	8	8
4 (5kg, 12)	0	0	6	8	12

한도를 초과하는 1번 물품 외에 나머지 물품들은 전부 들어갈 수 있다.

먼저 2번 물품이 한도 이내이므로 8을 적고, 3번 물품은 3kg 한도로 담을 때와 마찬가지로 가치가 2번 물품보다 가치가 떨어지므로 다시 8을 내려 적는다.

하지만 4번 물품은 한도 이내이며 직전 값보다 더 큰 가치를 지닌다. 따라서 최대값은 4번 물품의 12로 대체된다.

 

6. 담을 수 있는 무게 한도가 6kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0	0	0	0	13
2 (4kg, 8)	0	0	0	8	8	13
3 (3kg, 6)	0	0	6	8	8	13
4 (5kg, 12)	0	0	6	8	12	13

모든 물건이 한도 이내이므로 들어갈 수 있다.

하지만 한도 이내이면서 가치를 최대로 갖는 물품은 1번 물품 뿐이다. 따라서 dp[1 ~ 4][6]은 전부 13으로 채워진다.

 

7. 담을 수 있는 무게 한도가 7kg

물품(i) / 무게 한도(j)	1kg	2kg	3kg	4kg	5kg	6kg	7kg
1 (6kg, 13)	0	0	0	0	0	13	13
2 (4kg, 8)	0	0	0	8	8	13	13
3 (3kg, 6)	0	0	6	8	8	13	14
4 (5kg, 12)	0	0	6	8	12	13	14

모든 물건이 한도 이내이므로 들어갈 수 있다.

먼저 1번 물품을 넣어서 6kg를 채우는 경우, 남는 1kg를 더 채울 물품이 없으므로 1번 물품을 넣었을 때가 최대값이다. 13을 내려적는다.

 

3번 물품을 넣을 때를 주목해서 보아야 한다.

7kg 한도의 배낭에 3kg 물품을 넣었을 경우, 배낭의 한도는 4kg이 남고, 남은 물품 중 4kg를 채울 수 있는 방법, 2번 물품이 존재한다.

따라서 2번 물품을 넣고 4kg를 채우는 경우에 3번 물품을 넣고 3kg를 채우는 경우를 더해야 한다.

(

dp[i][j] = dp[i - 1][j - vw[i].first] + vw[i].second,

dp[3][7] = dp[2][7 - (3번 물품의 무게) 3] + (3번 물품의 가치) 6 = dp[2][4] + 6 = 8 + 6 = 14

)

즉 14와 기존 dp[2][7] = 13과 비교하여 더 큰 14가 dp[3][7]에 들어가야 하는 최대값이다. 

 

그 최대값 14가 5kg 물건을 넣는 경우, 12의 가치보다 크므로 14를 그대로 내려 적는다.

 

위 과정을 통해 알 수 있는 점화식은 두 개다.

 

1. 물품 i의 무게가 배낭에 담을 수 있는 무게의 한도(j) 이내인 경우 (vw[i].first < j)

dp[i][j] = max(dp[i - 1][j - vw[i].first] + vw[i].second, dp[i - 1][j])

이전 물품을 담는 경우 현재 무게 한도 - 현재 물품의 무게 한도를 가지는 값 + 현재 물품의 가치를 더한 값 & 이전 물품을 넣고 현재 한도만큼 채울 때의 값을 비교하여 최대값을 담는다.

 

2. 물품 i의 무게가 배낭에 담을 수 있는 무게의 한도(j)를 벗어나는 경우

dp[i][j] = dp[i - 1][j]

이전 값을 그대로 내려받는다.

Code

#include<bits/stdc++.h>

using namespace std;

int n, k;
int dp[101][100001];
vector<pair<int, int>> wv;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;

    wv.push_back({0, 0});

    for(int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;
        wv.push_back({weight, value});
    }

    for(int i = 1; i <= n; i++) {
        //물건의 갯수만큼 반복한다.
        for(int j = 1; j <= k; j++) {
            //물건을 담을 수 있는 가방의 무게 한도

            if(wv[i].first > j) {
                //i번째 물건의 무게가 현재 한도보다 크다면 담을 수 없다.
                dp[i][j] = dp[i - 1][j];
            } else {
                //담을 수 있다면
                dp[i][j] = max(dp[i - 1][j - wv[i].first] + wv[i].second, dp[i - 1][j]);
            }
        }
    }

    cout << dp[n][k] << "\n";

    return 0;
}

 

12865번: 평범한 배낭