Description

给定 $n$ 件物品，求质量不超过 $m$ 的前提下的最大价值。

Solution

01 背包问题，主要的是一行状态转移

$$f[j] = \max(f[j], f[j - w[i]] + v[i])$$

Code

#include <bits/stdc++.h>

using namespace std;

int f[20000];
int n, m;
int w[3500], v[3500];

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