12865번: 평범한 배낭

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

12865번: 평범한 배낭

각 물건의 무게와 가치를 입력받은 뒤, 현재 물건의 무게 W와 버틸 수 있는 무게 K에 대해 W <= w <= K인 모든 무게 w에 대해 기존 w에서의 최대 가치와 기존 (w - W)에서의 최대 가치 + 현재 물건의 가치 V를 비교해 최댓값을 갱신한다. 이 때, w는 K부터 1씩 줄여가며 비교해야 하는데, 그 이유는 w를 증가하는 방향으로 계산했을 때 현재 물건을 두 번 이상 포함시킬 가능성이 있기 때문이다.

#include <cstdio>

#define MAX_K 100000

int max(int a, int b) { return a > b ? a : b; }

int main() {
    // N: 물건의 개수, K: 버틸 수 있는 무게, W, V: 각 물건의 무게와 가치
    // val[w]: 가방에 무게가 w만큼 차 있을 때 가질 수 있는 가장 큰 가치
    int N, K, W, V, val[MAX_K + 1] = { 0, };
    
    // 각 물건에 대해
    for (scanf("%d %d", &N, &K); N--; ) {
        // 물건의 무게와 가치를 입력받은 뒤
        scanf("%d %d", &W, &V);
        // 현재 물건을 사용했을 때 같은 무게를 사용해 가치의 최댓값을 갱신 가능하다면 갱신
        for (int w = K; w >= W; w--)
            val[w] = max(val[w], val[w - W] + V);
    }

    printf("%d\n", val[K]);

    return 0;
}