[BOJ - 12865] 평범한 배낭 (C++)

  문제

  접근방법

 현재 무게가 w인 경우 최대 가치를 배열의 인덱스(w)로 갱신하면서 접근 -> DP

 

  코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, K;  // N: 물건 수, K: 최대 무게
    cin >> N >> K;

    vector<int> weight(N + 1);
    vector<int> value(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> weight[i] >> value[i];
    }

    // dp[w] -> 무게 w일 때 최대 가치
    vector<int> dp(K + 1, 0);

    for (int i = 1; i <= N; i++) {
        for (int w = K; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);
        }
    }

    cout << dp[K] << "\n";
    return 0;
}

  링크

12865번: 평범한 배낭