题目描述

如题

算法1

(dp) $O(n^2)$

blablabla

时间复杂度分析：很显然

C++ 代码

#include <bits/stdc++.h>
const int maxn = 2e3 + 10;

template <typename T>
inline void read(T &s) {
    s = 0;
    T w = 1, ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }
    while (isdigit(ch))  { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
    s *= w;
}

int n;
int av;
int am;
int v[maxn];
int w[maxn];
int val[maxn];
int f[maxn][maxn];

int main() {
    read(n), read(av), read(am);
    for (int i = 1; i <= n; ++i) {
        read(v[i]);
        read(w[i]);
        read(val[i]); 
    }

    f[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = av; j >= v[i]; --j) {
            for (int k = am; k >= w[i]; --k) {
                f[j][k] = std::max(f[j][k], f[j - v[i]][k - w[i]] + val[i]);
            }
        }
    }

    printf("%d\n", f[av][am]);
    return 0;
}