문제

풀이 요약

냅색 문제.

풀이 상세

1. 최대무게인 $K$ 부터 시작하여, 현재 무게와 아이템 무게를 비교한다.

2. 만약 임의의 가방 무게 $K_j$ 에서 가져올 수 있는 $dp$ 값이 존재한다고 하자. 만약 다음 아이템의 무게를 구하는 중, 현재 가방의 무게를 뺐을 때 임의의 가방 무게 $K_j$ 의 $dp$ 값에 도달한다면 이는 현재 가방 무게에서 두 아이템의 가칫값을 더하는 것이 가능하다는 것을 의미한다.

정답

#include <bits/stdc++.h>
using namespace std;
int dp[100004];
int items[100004][2];
int N, K;
int main() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> items[i][0] >> items[i][1];
        for (int j = K; j >= 1; j--)
            if (items[i][0] <= j)
                dp[j] = max(dp[j], dp[j - items[i][0]] + items[i][1]);
    }
    cout << dp[K];
}