一道较为基础的背包dp题

不会背包dp的人看这里 我们设dp[i]表示重量为i的最大价值，从而可以很轻松的想出：

这要从目标重量一直到第i个重量进行降序，从而 dp[j] = max(dp[j], dp[j - v] + w);

v为重量，w为价值

知道这些后，可以轻松写出AC解：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int T, n, P, Q, dp[N];
bool flag;
int main () {
    cin >> T;
    while (T--) {
        flag = false;
        memset(dp, 0, sizeof(dp));
        cin >> n >> P >> Q;
        for (int i = 1, p, c; i <= n; i++) {
            cin >> p >> c;
            for (int j = Q; j >= c; j--) {
                dp[j] = max(dp[j], dp[j - c] + p);
            }
        }
        for (int i = 0; i < N; i++) {
            if (dp[i] >= P) {
                cout << i << "\n";
                flag = true;
                break;
            }
        }
        if (!flag) cout << "-1\n";
    }
    return 0;
}

本人若狗一个，不喜勿喷