题目描述

01背包啊

样例

blablabla

题解

一维数组优化。
f[]表示当前体积下最大的价值。
dp就很显然了$f[j] = max(f[j], f[j - w[i]] + v[i])$
这里的w为体积， v为价值
第二层循环要倒序，保证该物体只选一次。

C++ 代码

#include <bits/stdc++.h>
const int maxn = 2e3 + 100;
typedef long long LL;

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 m;
int w[maxn];
int v[maxn];
int f[maxn];

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(w[i]), read(v[i]);

    // std::memset(f, 0xcf, sizeof(f));
    f[0] = 0;

    for (int i = 1; i <= n; ++i) {
        for (int j = m; j >= w[i]; --j) {
            f[j] = std::max(f[j], f[j - w[i]] + v[i]);
        }
    }
    printf("%d\n", f[m]);
    return 0;
}