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

12865 평범한 배낭

12865번: 평범한 배낭

C

#include <stdio.h>
#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int DP[103][100003];
int w[103];
int v[103];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &w[i], &v[i]);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j - w[i] >= 0)
                DP[i][j] = MAX(DP[i - 1][j], DP[i - 1][j - w[i]] + v[i]);
            else DP[i][j] = DP[i - 1][j];
        }
    }
    printf("%d\n", DP[n][k]);

    return 0;
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int DP[103][100003];
int w[103];
int v[103];

int main() {
    ios::sync_with_stdio(0);
    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] >= 0)
                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] << '\n';

    return 0;
}

 

w[i]는 i번째 물품의 무게, v[i]는 i번째 물품의 가치이다.

DP[i][j]는 1번째부터 i번째 물품까지 보았을 때, 담은 물품들의 무게의 합이 j인 경우의 가치 합이다.

DP[i][j]를 구하는 데 있어, 두 가지 경우로 나눌 수 있는데

i번째 물건을 담은 경우는 DP[i - 1][j - w[i]] + v[i]와 같고

i번째 물건을 담지 않는 경우는 DP[i-1][j]와 같다.