P1507 NASA的食物计划

Link

Solution

多了一维限制的01背包

Code

#include <algorithm>
#include <iostream>
const int maxn = 500 + 10;
using namespace std;

int vol[maxn], qul[maxn], kal[maxn], f[maxn][maxn];

int main() {
    int v, n, m;
    cin >> v >> m >> n;
    for (int i = 1; i <= n; i++)cin >> vol[i] >> qul[i] >> kal[i];
    for (int i = 1; i <= n; i++)
        for (int j = v; j >= vol[i]; j--)
            for (int k = m; k >= qul[i]; k--)
                f[j][k] = max(f[j][k], f[j - vol[i]][k - qul[i]] + kal[i]);
    cout << f[v][m] << endl;
    return 0;
}