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

 

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

 

 

---

 

제목을 보면 알 수 있듯이 그 유명한 배낭 문제이다.

 

먼저 입력을 살펴보면

N: 물건의 개수 (1 ~ 100) 10^2

W: 각 물건의 무게 (1 ~ 100,000) 10^5

V: 각 물건의 가치 (0 ~ 1,000) 10^3

K: 가방 속 최대무게 (1 ~ 100,000) 10^5

 

문제에서 원하는 출력은

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

 

시간 제한은 2초이므로 10^8까지는 연산해도 괜찮다.

 

 

<풀이>

DP 문제이므로 dp 배열을 만들고 각 값이 의미하는 바를 설정하는 게 중요하다.

이 문제는 배낭 문제이므로 2차원 배열을 사용한다.

 

dp[i][j]가 있을 때,

i: 임의로 설정한 각 물건의 번호로 1부터 N까지 반복한다.

j: 가방 속에 들어갈 수 있는 최대 무게로 1부터 K까지 반복한다.

dp[i][j]: i번째 물건까지 사용할 수 있을 때, j 무게까지의 가치합의 최댓값

위와 같이 설정하면 문제를 해결할 수 있다.

 

N은 10^2, K는 10^5까지 가능하므로 O(N * K) = 10^7으로 시간 범위 이내이다!

 

점화식

만약 j가 W[i] 이상이라면? i번째 물건을 가방 속에 집어넣을 수 있다는 뜻이다.

즉, i번째 물건을 넣지 않았을 때와 i번째 물건을 넣었을 때를 비교해야 한다.

넣었을 때에는 '배낭의 무게가 j-W[i]일때의 가치'와 배낭에 i번째 물건을 넣었으므로 V[i](i번째 물건의 가치)를 더해줘야 한다.

 

이걸 코드로 구현하면 다음과 같다.

if(j >= W[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);

 

만약에 j가 W[i] 미만이라면? i번째 물건을 가방 속에 집어넣을 수 없다.

그렇다면 그냥 i-1번째 값에서 가져오면 된다.

 

이걸 코드로 구현하면 다음과 같다.

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

 

예제의 입력을 통해 시뮬레이션을 돌려보자.

4 7 //n, k
6 13
4 8
3 6
5 12

 

먼저 첫 번째 물건은 무게가 6, 가치가 13이다.

이 경우 다음과 같이 채워진다.

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

 

두 번째 물건을 보자.

무게가 4, 가치가 8이다.

	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

dp[2][6]에서 max를 통한 비교가 일어나 2번째 물건을 넣지 않았을 때 값이 더 크므로 위의 값을 가져온다.

 

세 번째 물건을 보자.

무게가 3, 가치가 6이다.

	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

마지막 dp[3][7]이 핵심이다!

if(j >= W[i]) dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i]);

위의 코드에 따라 max(dp[2][7], dp[2][4] + V[3])을 했을 때

max(13, 8 + 6) = max(13, 14) = 14

세 번째 물건을 넣었을 때 가치가 더 커지므로 넣은 값을 최댓값으로 한다!

 

마지막 물건을 보자.

무게가 5, 가치가 12이다.

	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	0	0	6	8	12	13	14

 

결과적으로 dp[n][k]인 dp[4][7]을 출력해주면 가치합의 최댓값을 출력할 수 있다!

 

 

 

코드 전체를 보면 다음과 같다.

#include <iostream>
using namespace std;

int W[105], V[105];
int dp[105][100005];

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

    int n, k;
    cin>>n>>k;

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

    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];
        }
    }

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