BOJ 12865 - 평범한 배낭

10 May 2024 in Posts on Random, CPP

“배낭 문제”

BOJ 12865 - 평범한 배낭
- 문제 링크

BOJ 12865 - 평범한 배낭

문제 링크

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int INF = 0x3f3f3f3f;
using namespace std;

int N, K;
int w[110];
int v[110];
int dp[110][100010];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    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 (w[i] <= j)
                dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
            else
                dp[i][j] = dp[i - 1][j];
        }
    }

    cout << dp[N][K];
    return 0;
}

다이나믹 프로그래밍 유형 문제 중 아주아주 유명한 배낭 문제(Knapsck problem)이다. 푼지는 오래됐는데 자꾸 까먹기도 하고, 이 문제가 배낭 문제 중에서 가장 표준적이고 그나마 쉽다고(?) 할 수 있을 것 같아서 따로 기록을 남긴다.
대중적으로 알려진 풀이는 물건의 번호를 X축, 수용할 수 있는 무게를 Y축으로 한 이차원 정수 배열(int dp[number][weight])에 해당 물건의 번호(number)까지, weight만큼 수용할 수 있을 때의 최대값을 기록해나가는 것이다. 이때 이전에 memo해 두었던 값을 참조하여 시간 복잡도를 줄인다. 아래 표에 대해서 알 것이다. n은 물건의 번호, k는 수용할 수 있는 무게이며, dp[n][k]의 값은 해당 좌표의 최대 가치 값이다.

그리고 아래는 이차원 배열을 유도하는 점화식이다.

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= K; j++) {
        if (w[i] <= j)
        // i 번째 물건을 넣는 경우(넣는 경우와 안 넣는 경우의 대소 비교)
            dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
        else
        // i 번째 물건을 넣지 않는 경우(못 넣는 경우)
            dp[i][j] = dp[i - 1][j];
    }
}

표와 점화식만으로는 직관적인 이해가 어렵다. 점화식을 이해하기 위해 표에서 주목해야할 부분은 아래와 같다.

물건 1, 2, 3, 4가 차례대로 6, 4, 3, 5의 무게와 13, 8, 6, 12의 가치를 지니므로 dp[3][7]은 14가 맞다. 세 번째 물건까지를 배낭에 넣을 수 있다고 쳤을 때 첫 번째 물건 하나만 넣는 것보다(무게 6, 가치 13), 두 번째 물건과 세 번째 물건을 둘 다 넣는게 가치가 더 높기 때문이다(무게 4, 3 => 7 / 가치 8, 6 => 14). 어떻게 이것을 판별할 수가 있을까?
dp[2][7]에서 dp[3][7]로 넘어가는 과정에서 바뀌는 것은 세 번째 물건을 선택지에 넣을 수 있게 되는 것이다. 즉 dp[3][7]을 만드는 경우의 수는 두 가지로 첫 번째는 세 번째 물건을 넣는 것이고, 두 번째는 세 번째 물건을 넣지 않는 것이다.
세 번째 물건을 넣지 않는 경우는 두 가지가 있는데 첫 번째는 세 번째 물건의 무게가 해당 수용 가능한 무게보다 큰 경우(w[3] > 7, 만약 위 예시에서 세 번째 물건의 무게가 3이 아니라 8이라면 넣을 수가 없었을 것이다)이고, 두 번째는 세 번째 물건을 넣었을 때보다 넣지 않았을 때 최대 가치가 더 큰 경우이다(점화식의 max 판별 부분, 만약 위 예시에서 세 번째 물건의 가치가 6이 아니라 4였다면 그냥 첫 번째 물건만 넣는게 가치가 더 컸을 것이다(13 > 12)).
세 번째 물건을 넣지 않는 점화식은 dp[i - 1][j]이다. 어차피 세 번째 물건을 넣지 않을 것이기 때문에 두 번째 물건까지만 따졌을 때의 최댓값을 그대로 끌어온다.
dp[3][7]에서 세 번째 물건을 넣을 때의 최댓값을 어떻게 판별할 수 있을까? 점화식을 그대로 가져와서 생각해보자. dp[2][7 - w[3]] + v[3]이 세 번째 물건을 넣어서 dp[3][7]을 최대치로 만드는 식이다(w[3] = 3, v[3] = 6). 세 번째 물건(무게 3)을 살포시 얹어서 7이라는 무게를 완성시키려면 dp[2][4] 에 세 번째 물건을 얹기만 하면 될 것이다. dp[2][4]는 두 번째 물건까지 넣을 수 있고, 최대 수용 무게가 4일때의 최대 가치라는 사실이 보장되어있기 때문에 여기에 그냥 세 번째 물건을 얹기만 하면 반드시 최대치인 dp[3][7]이 나올 것이라는 사실 또한 자명하다.
따라서 dp[3][7]의 최댓값을 구하기 위해서는 세 번째 물건을 넣지 않는 경우 (dp[2][7] = 13)과 넣는 경우 (dp[2][7 - w[3]] + v[3] = 14)를 비교하게 되는 것이다. 물론 아까 말한 것처럼 세 번째 물건이 최대 수용 무게인 7보다 크다면 항상 세번째 물건을 넣지 않는 경우만을 계산하게 된다.
이것은 무게가 k일 때도 성립하며, 다시 쓰자면 점화식은 아래와 같다.

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= K; j++) {
        if (w[i] <= j)
        // i 번째 물건을 넣는 경우(넣는 경우와 안 넣는 경우의 대소 비교)
            dp[i][j] = max(dp[i - 1][j - w[i]] + v[i], dp[i - 1][j]);
        else
        // i 번째 물건을 넣지 않는 경우(못 넣는 경우)
            dp[i][j] = dp[i - 1][j];
    }
}

BOJ 12865 - 평범한 배낭

BOJ 12865 - 평범한 배낭

문제 링크

나는 gyopark

Error

BOJ 12865 - 평범한 배낭

문제 링크

Templates (for web app):

Error