[C++] 12865: 평범한 배낭

🖍️ 겪은 문제

• 문제 해결 아이디어가 안떠올랐다. 완전 탐색으로 풀면 시간 초과였다. 역시나 DP였다.

🔍 해결 방법

• DP최소 단위를 설계한다.
  • dp[n]을 n무게일 때 최대 가치라고 하자.
• 점화식을 세운다.
  • dp[i] = max(dp[i], dp[i - weight[i]] + value[i]);
• 포인트는 순회를 거꾸로 K에서부터 1씩 줄여나가며 한다는 것이다.
  • 1에서 부터 돌면 점화식에서 더 작은 값을 이용하기 때문에, 이미 계산한 물건을 또 담을 수 있다.

📇 코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N, K;
    cin >> N >> K;

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

    vector<int> dp(K + 1, 0);
    for (int i = 0; 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;
}