[백준(BOJ)] 12865번: 평범한 배낭 (C++)

Knapsack 알고리즘

DP[물건 번호][무게] = 최대 가치 -> 해당 물건에서 최대 무게를 가질 때 가질 수 있는 최대 가치에 해당

첫 번째 물건부터 무게 1부터 최대 무게 K까지 무게를 담았을 때 가질 수 있는 최대 가치를 DP에 저장한다. 이 정보는 다음 물건에서 최대 무게-다음 물건 무게가 이전에서 담을 수 있는 최대 무게에서 최대 가치를 가질 것이므로 이때의 가치와 다음 물건의 가치를 더했을 때와 이전 물건에서 최대 가치 중 최댓값을 취할 때 사용한다.

만약 i번째 물건의 무게가 최대 무게 j보다 작은 경우엔 담을 수 없으므로 i-1번째의 최대 무게 j에서의 최대 가치를 취한다. 

최종적으로 마지막 물건에서 가질 수 있는 최대 무게에서의 최대 가치가 배낭에 넣을 수 있는 물건들의 가치합의 최댓값이 된다.

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int N,K;

    scanf("%d %d", &N, &K);
    vector< pair<int, int> > items(N+1,make_pair(0,0));
    vector< vector<int> > DP(N+1, vector<int>(K+1)); // [물건 번호][무게] = 최대 가치

    for(int i=1; i<=N; i++){
        scanf("%d %d", &items[i].first, &items[i].second);
    }

    for(int i=1; i<=N; i++){
        int weight = items[i].first;
        int value = items[i].second;
        for(int j=1; j<=K; j++){ // 최대 담을 수 있는 무게를 하나씩 늘려감
            if(j-weight >= 0) DP[i][j] = max(DP[i-1][j], DP[i-1][j-weight] + value);
            else DP[i][j] = DP[i-1][j]; // 현재 물건 무게가 더 크면 최대 가치는 이전 물건의 
        }
    }
    printf("%d\n", DP[N][K]);

    return 0;
}