题解 | 【模板】01背包

#include <stdio.h>
#include <string.h>

int main(void) {
    int n, V;
    scanf("%d%d", &n, &V);

    int v[1005], w[1005];
    for (int i = 0; i < n; i++)
        scanf("%d%d", &v[i], &w[i]);

    int f[1005];
    memset(f, -0x3f, sizeof(f));
    f[0] = 0;
    for (int i = 0; i < n; i++)
        for(int j = V; j >= v[i]; j--)
            f[j] = (f[j] > f[j - v[i]] + w[i]) ? f[j] : f[j - v[i]] + w[i];

    //要求1
    int ans1 = 0;
    for(int i = 0; i <= V; i++)
        ans1 = (ans1 > f[i]) ? ans1 : f[i]; 
    
    //要求2
    int ans2 = 0;
    if(f[V] < 0)    ans2 = 0;
    else    ans2 = f[V];

    printf("%d\n%d\n", ans1, ans2);
    return 0;
}