BOJ 12865 평범한 배낭과 냅색

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

12865번: 평범한 배낭

 

냅색(배낭 문제)라는 개념을 모르면 문제를 해결하기 어려운 경우가 많습니다.

냅색은 꽤나 유명한 다이나믹 프로그래밍의 응용입니다.

 

문제의 예제 입력1로 dp테이블을 만들면 아래와 같습니다.

 

 

테이블의 각 열에 적힌 숫자는 준서가 버틸 수 있는 배낭 무게의 한계입니다. 또한 행에는 각 물품이 적혀 있습니다. 여기서 중요한 점이 있습니다. 첫 행만 고려한다는 것은, 준서가 들고갈 수 있는 물품이 오직 물품1 밖에 없다는 것입니다. 두번째 행까지 고려한다는 것은, 준서가 들고갈 수 있는 물품이 물품1과 물품2, 총 두 개라는 뜻입니다. 네 번째 행까지 고려하면, 준서가 들고갈 수 있는 물품은 물품1~물품4입니다. 또한 테이블의 각 칸에 들어갈 수는 해당 상황에서 최대 가치입니다.

 

 

 

이렇게 행을 따라 내려오면서, 그 행을 포함한 그 위의 물품들만을 고려합니다.

그렇다면 표의 맨 오른쪽 아래 칸(준서가 버틸 수 있는 한계가 7이며, 물품1~4를 고려할 때)에 적힐 값이 문제의 답이 됩니다.

 

우리는 dp테이블을 위와 같이 순차적으로 채워나갈 것입니다.

 

 

 

테이블의 첫 행을 채우면 위의 모양이 됩니다. 준서가 버틸 수 있는 무게가 1~5일 때는, 물품1을 배낭에 넣을 수 없습니다. 그러나 6~7일 때는 물품1을 가져갈 수 있어 13의 가치를 얻을 수 있습니다.

 

 

 

 

두 번째 행을 채워야합니다. 준서가 버틸 수 있는 무게가 1~3일 때는 아무것도 가져갈 수 없습니다.

하지만 4부터는 물품2를 가져갈 수 있습니다. 그런데 버틸 수 있는 무게가 6일 때, 우리는 고민을 해야합니다. 물품1과 물품2 각각은 챙겨갈 수 있지만, 두 개를 동시에 배낭에 넣을 순 없기 때문입니다. 어떻게 결정해야 할까요?

 

아래에 나올 점화식은 이 문제의 가장 핵심입니다.

$DP[물품2][6] = max(DP[물품1][6], 물품2의 가치 + DP[물품1][6-(물품2의 무게)])$

 

 

천천히 해석해보면 다음과 같습니다. DP[물품2][6]은 지금 우리가 채울 칸을 의미합니다. 이 값은 max 함수에서 비교되는 두 값 중 하나로 결정됩니다.

 

첫 번째 비교값은 DP[물품1][6]입니다. 이 값은 물품2를 가져가지 않는 경우입니다. 물품2를 가져가지 않으니, 물품2를 없는 취급해도 됩니다. 물품2를 고려하지 않고, 준서가 버틸 수 있는 무게가 6일 때의 가치의 최댓값은 이미 구해놨습니다. 바로 이 값이 DP[물품1][6]입니다.

 

두 번째 비교값은 물품2의 가치 + DP[물품1][6-(물품2의 무게)] 입니다. 이 값은 물품2를 가져가는 경우입니다. 물품2를 가져가니, 일단 물품2의 가치를 얻을 수 있습니다. 그런데 물품2를 배낭에 넣고보니, 아직 여분의 무게(6-4=2)가 남는다는 것을 알 수 있습니다.

 

지금 경우에선 남는 무게로 추가로 챙길 수 있는 물품이 없지만, 혹시 DP 테이블을 채워가다보면 추가로 챙겨갈 수 있는 경우가 나올 수 있지 않을까요? 그 값이 바로 DP[물품1][6-(물품2의 무게)]입니다. 물품2는 이미 배낭에 넣어서 이제 없으니, 준서가 버틸 수 있는 무게가 2일 때 물품1만 고려하는 경우의 가치의 최댓값을 추가로 가져가는 것입니다.

 

 

이 식을 일반화하면 다음과 같습니다.

 

$DP[물품n][k] = max(DP[물품n-1][k], 물품n의 가치 + DP[물품n-1][k-(물품n의 무게)])$

 

이 식에 따라 dp테이블을 채워나가면 됩니다.

 

 

물품3 행에서 준서가 버틸 수 있는 무게가 7일 때의 값을 채우는 과정을 아래에서 살펴봅시다.

 

 

물품3을 챙기지 않는 경우, 우리는 최대 13의 가치를 챙길 수 있습니다. 그런데 물품3을 챙기면, 일단 물품3의 가치인 6을 챙깁니다. 또한 남는 무게가 7-3=4 입니다. 물품1~2를 고려하고, 준서가 버틸 수 있는 무게가 4일 때 우리는 최대 8의 가치를 챙길 수 있습니다. 그러므로 물품3을 챙기면 최대 6+8=14의 가치를 챙기는 것입니다. 그러므로 이 칸은 14로 채워집니다.

 

 

배낭 문제라는 유형을 모를 경우, 위와 같은 테이블을 주체적으로 생각해내는건 매우 어려울 것 같습니다.

이러한 DP 테이블 유형도 있다는 것을 기억해두면 좋을 것 같습니다.

 

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int dp[101][100001];
int value[101];
int weight[101];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    for(int i=1; i<=N; i++){
        cin >> weight[i] >> value[i];
    }	
    for(int k=1; k<=K; k++){
        dp[1][k] = (weight[1] <= k ? value[1] : 0);
    }
    for(int bag=2; bag<=N; bag++){
        for(int k=1; k<=K; k++){
            if(weight[bag] > k) dp[bag][k] = dp[bag-1][k];
            else dp[bag][k] = max(dp[bag-1][k], dp[bag-1][k-weight[bag]]+value[bag]);
        }
    }
    cout << dp[N][K];
}

 

배낭 문제 유형인 다른 문제들도 소개합니다.

 

 

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

11047번: 동전 0

 

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

2293번: 동전 1

 

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

9084번: 동전

 

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

3067번: Coins

 

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

22839번: Square Coins