12865: 평범한 배낭

문제

• https://www.acmicpc.net/problem/12865
• 분류: 동적프로그래밍

Before

• 위 링크에서 제공한 예를 기준으로 설명합니다.
• 물건의 갯수 = 4
• 물건을 담을 수 있는 최대 무게 = 7

아래는 문제에 제공된 테스트 케이스를 정리한 표입니다.

물건의 무게	물건의 가치
6	13
4	8
3	6
5	12

핵심: DP 배열

동적 프로그래밍에서 가장 핵심이 되는 내용은 DP 배열을 어떻게 정의하고 풀어내는가 라고 생각합니다.
해당 문제에서는,

• 2차원 DP배열을 정의하며,
• DP[i][j]를 기준으로
  • i는 위 표에서 이야기 하는 물건,
  • j는 가방의 사이즈 입니다.
    • 즉, 해당 테스트 케이스에서는 가방의 사이즈 1~7까지 모두 고려합니다.
  • 최종적으로 이야가히고자 하는 DP는, DP[i][j] = i번째 물건과, 가방의 사이즈가 j만큼일 때 넣을 수 있는 최대 가치 입니다.
• 따라서 해당 문제에서는 DP[4+1][7+1] 사이즈의 DP 배열을 생성하게 됩니다.
  • 각각 +1이 된 경우는, 0도 고려를 했기 때문입니다.
    i.e: 물건이 없는 경우, 가방이 없는 경우..

DP - 초기화

• 기본적으로 각 물건이 0개일때, 가방의 사이즈가 0인 경우는 모두 0으로 초기화 해 줍니다.

다음은 0으로 초기화 한 결과입니다.

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

DP - i = 1[첫 물건]

첫 물건의 무게 가치는 '6' 입니다. 즉, 배낭의 사이즈가 6 미만인 친구들은 모두 0으로 초기화 됩니다.
[즉, 배낭의 사이즈가 6 미만이면 담을 수가 없습니다!]

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

그러면 6부터는 어떻게 되는지 보면, 배낭의 사이즈가 6이면 무게가 6인 물건을 담을 수 있습니다!
배낭의 사이즈가 7인 경우도 보면, 무게가 6인 물건을 동일하게 담을 수 있죠.

다만, 현재 무게와 이 전에 담았던 무게를 같이 비교해야되는데요,
가령, 배낭의 사이즈 7인 경우를 보면 두가지 경우가 존재하는데요,

• 이 전에 담았던 물건[i-1]에서 지금 담으려고 하는 물건의 무게를 뺀[j-w[i]] 다음에 가치를 더한 경우
• 그냥 이 전에 담았던 물건의 가치를 사용하는 경우

두 가지 경우가 있습니다.
해당 DP배열은 [i][j]에서 최대한 많은 가치를 가지고 있는 경우라고 지정 하였습니다.
그렇기 때문에 이 전에 담았던 물건[i-1]에서 지금 담으려고 하는 물건의 무게를 뺀[j-w[i]] 이 문구는 dp[i-1]j-w[i]]를 의미하며, 해당 원소는 가능한 최대의 가치를 지니게 됩니다. 여기에 현재 가방에 넣고자 하는 물건을 넣어 봐서 dp[i-1][j]랑 비교를 해 보자는 의미입니다. 큰 수가 결국에 들어가게 되겠죠.

해당 예제에서 배낭의 사이즈가 7인 경우를 살펴보면[Let i = 1, j = 7, w[i] = 6, v[i] = 13]
dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
해당 점화식이 성립합니다.
보면, dp[i-1][j]는 0을 가리키고, v[i] + dp[i-1][j-w[i]]는 13을 가리킵니다. 더 큰 수는 후자이므로, 13으로 업데이트가 되는 것이죠.

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

DP - i = 2[2번째 물건]

위 예제와 동일하게, 배낭의 무게가 4가 되지 않는 한 물건을 담을 수 없습니다.
배낭의 무게가 3이 될 때 까지는 모두 0으로 초기화 해 줍니다.

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

배낭의 무게가 4 부터는
dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
해당 점화식을 일단 적용해 나갑니다.

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

DP - i = 3[3번째 물건]

여기서 위 말했던 점화식이 드디어 왜 쓰이는지 예제로 볼 수 있는 구간입니다.
일단 배낭의 사이즈가 6번까지는 똑같이 진행 됩니다.

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

7번째 배낭의 경우를 한번 보면, v[i] + dp[i-1][j-w[i]] = 14입니다.
dp[i-1][j] = 13보다 큽니다. 따라서 14로 값을 업데이트 해 줍니다.
여기서의 판단은 다음과 같습니다.

2번째 물건과, 배낭의 사이즈가 7인 경우에는 1번째 물건 하나 넣는게 좋았음!

어? 근데 3번째 물건을 보니까 배낭의 사이즈가 7인 경우에는 2번째 물건 하나와 3번째 물건 하나 더 넣는게 더 좋네? 이걸로 가자!

그래서 해당 점화식을 적용하고, 거기에서 max를 취해 가장 가치가 높은 값을 고르게 되는 것입니다.!

DP - 그 이후

위 설명했던 방식 그대로 식을 이어나갑니다.

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

이후에 가장 마지막 원소를 출력하면 정답을 맛보게 됩니다!

코드

#include <iostream>
#include <vector>

using namespace std;

class ThingInfo {
public:
    int weight;
    int value;
};

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

    int things_size, max_weight;
    cin >> things_size >> max_weight;
    vector<ThingInfo> reference(things_size+1);
    for (int i = 1; i <= things_size; i++) {
        cin >> reference[i].weight;
        cin >> reference[i].value;
    }

    vector<vector<int>> dp(things_size+1, vector<int>(max_weight+1, 0));

    for (int i = 0; i <= max_weight; i++) {
        dp[0][i] = 0;
    }

    for (int i = 0; i <= things_size; i++) {
        dp[i][0] = 0;
    }

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

    cout << dp[things_size][max_weight] << endl;
    
    return 0;
}