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

배낭 문제의 기본

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

12865번: 평범한 배낭

 

배낭문제에서 생각해야할 점은 현재 가지고 있는 무게가 과연 최대로 담을 수 있는 무게인지를 생각하면 된다.

 

가장 처음 접근했던 방법은 물체의 개수를 늘려가며 무게를 넘지 않는 선에서 최대값을 구하려 했다.

무슨 말이냐면,

물체 하나로 얻을 수 있는 가치의 최댓값은 무게 6일 때의 가치인 13.

물체 두 개를 합쳐 얻을 수 있는 가치의 최댓값은

무게 6 + 4 일때 가치 21

무게 6 + 3 일때 가치 19

무게 6 + 5 일때 가치 25

무게 4 + 3 일때 가치 14

무게 4 + 5 일때 가치 20

무게 3 + 5 일때 가치 18

등 물체의 개수를 늘려가며 가치의 합을 구하고,

이를 계산함과 동시에 무게를 넘는지를 판단하는 식으로 계산하려 했다.

 

하지만 알고보니 이는 더욱 쉽게 이차원 배열로 문제 접근이 가능했다.

예제 문제를 표로 정리하면 다음과 같다.

n      \       k	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	8	13	14

 

무게를 늘려가며 물체를 집어 넣었을 때, 남는 무게에 또 다른 물체를 집어넣을 수 있는지 판단하는 구조이다.

즉, k 값을 1씩 늘려가며 n번 째 물체를 집어 넣음과 동시에 남는 자리에 또 다른 물체를 집어 넣을 수 있는지 판단한다.

이를 위해서는 k 값이 n번째 물체의 무게인 w[n]보다 커야하며, w[n]보다 작을때에는 그 이전 물체를 집어넣었을 때의 최댓값으로 초기화시켜주면 된다.

만약 k 값이 n번째 물체의 무게인 w[n]보다 클 때에는 그 이전 물체를 집어넣었을 때의 최댓값과 비교함과 동시에 n번째 물체의 가치인 v[n]과 물체의 무게가 k - w[n] 인  물체의 가치의 합과 비교해가며 최댓값을 설정해주면 된다.

 

#include <iostream>
using namespace std;
int dp[1001][100001];
int w[100001];
int v[1001];
int main() {
    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++){
            w[i]>j ? dp[i][j]=dp[i-1][j] : dp[i][j]=max(dp[i-1][j], v[i]+dp[i-1][j-w[i]]);
        }
    }
    /* for(int i=1; i<=n; i++){
        for(int j=1; j<=k; j++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    } */
    cout << dp[n][k];
}