[C++] 백준 12865: 평범한 배낭

문제 이해

- 배낭 문제

- N개의 물건이 있으며, 각 물건은 무게 W와 가치 V를 가진다.

- 준서가 들 수 있는 무게는 최대 K이다.

- 배낭에 넣을 수 있는 가치합의 최댓값을 구하라.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 512MB

 

<입력>

- N: 물품의 수 (1 ~ 100, 10^2)

- K: 버틸 수 있는 무게 (1 ~ 100,000, 10^5)

- W: 무게 (1 ~ 100,000, 10^5)

- V: 가치 (0 ~ 1,000, 10^3)

 

<출력>

- 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력하라.

 

 

---

문제 풀이

이 문제는 배낭 문제의 제일 기본 문제이다.

꼭 숙지해서 비슷한 유형에 적용할 수 있도록 하자!

 

 

먼저 배낭 문제는 DP 문제이다.

DP이니만큼 배열의 인덱스와 값을 잘 설정하는 게 중요할 것이다.

 

 

배낭 문제는 

i: 물건의 종류
j: 가방의 무게
dp[i][j]: i번째 물건까지 사용했을 때, j 무게까지 가치합의 최댓값

이렇게 설정하여 풀 수 있다.

 

 

또한 배낭 문제는 배열을 채울 때 이전 물건까지의 배열값을 이용한다.

이 점을 유의해서 코드를 살펴보도록 하자.

 

 

핵심 코드는 바로 아래와 같다.

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= k; j++){
        if(stuff[i].weight <= j){
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-stuff[i].weight] + stuff[i].value);
        }else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

 

먼저 i는 물건의 종류라고 했다.

그렇기에 i는 1번 물건부터 n번 물건까지 탐색한다.

 

이때 0이 아닌 1을 인덱스로 사용하는 것은

위에서 말했다시피 이전 물건까지의 배열값을 이용하기에

0을 시작으로 할 경우 배열에서 이전 물건에 접근할 수 없게 된다.

 

 

j는 배낭의 무게 한도이다.

무게 한도를 조절해가며 i번째 물건을 넣을 수 있는지 없는지 판별한다.

 

이때, 만약 넣는 게 가능하다면

j 무게에서 i-1번째 물건까지의 가치합 dp[i-1][j]와

j - stuff[i].weight 무게, 즉, i번째 물건을 넣을만큼의 무게가 비어있을 때의 가치의 합 dp[i-1][j - stuff[i].weight]

+ i번째 물건의 가치 stuff[i].value를 비교해주는 것이다.

 

 

만약 넣는 게 불가능하다면

이전 물건에서의 가치합의 최댓값을 그대로 반영해준다.

 

 

이해를 돕기 위해 예제를 사용해보자.

4 7
6 13
4 8
3 6
5 12

문제에서의 예제이다.

 

i = 1

	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2
3
4

 

j값이 6이 될 때 조건문을 만족해 첫 번째 물건을 넣는 경우로 최댓값이 갱신될 것이다.

7일 때도 동일하다.

 

 

i = 2

	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3
4

 

j값이 4가 되었을 때 조건문이 성립해 두 번째 물건을 넣는 경우로 갱신된다.

5가 되었을 때도 동일하다.

 

이후 j가 6이 되면,

'dp[1][6]'과 'dp[1][2(6-4)] + 2번째 물건의 가치'를 비교했을 때 dp[1][6]이 13으로 크므로

dp[1][6]의 값으로 갱신된다.

7이 되어도 위와 같을 것이다.

 

 

i = 3

	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4

 

i = 1, 2일때와 같이 진행되다가

 

j = 7일때 중요한 포인트가 등장한다.

3번째 물건의 무게는 3이고 가치는 6이다.

max(dp[2][7], dp[2][7-3] + 6) = max(13, dp[2][4] + 6) = max(13, 8 + 6) = max(13, 14) = 14

 

j가 7이 되었을 때, 3번째 물건을 넣는 것이 이전 물건까지의 가치합보다 크기에 갱신을 해주는 것이다!!

 

위 사실을 잘 이해한다면 배낭 문제를 잘 이해했다고 볼 수 있다.

 

 

 

배낭 문제는

i: 물건의 종류
j: 가방의 무게
dp[i][j]: i번째 물건까지 사용했을 때, j 무게까지 가치합의 최댓값

배열을 채울 때, i-1번째의 배열값을 이용한다.

 

위의 두 사실만 잘 인지하고 있는다면 쉽게 풀 수 있을 것이다!!

 

 

---

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
#define INF 987654321

struct Stuff{
    int weight;
    int value;
};

vector <Stuff> stuff;
int dp[105][101010];

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

    int n, k;
    cin>>n>>k;
    stuff.push_back({0, 0});
    for(int i = 0; i < n; i++){
        int w, v;
        cin>>w>>v;
        stuff.push_back({w, v});
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(stuff[i].weight <= j){
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-stuff[i].weight] + stuff[i].value);
            }else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout<<dp[n][k];
    return 0;
}

 

 

 

---

배운 점

유명한 배낭 문제에 대해서 익힐 수 있었다!