C

二维朴素 dp

#include <stdio.h>

#define MAXSIZE 1010
#define max(a,b) ((a)>(b)?(a):(b))
int N, V, v[MAXSIZE], w[MAXSIZE], dp[MAXSIZE][MAXSIZE];

void init() {
    scanf("%d%d", &N, &V);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", v+i, w+i);
    }
}

int main() {
    init();

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= V; ++j) {
            dp[i][j] = dp[i-1][j];
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }
    }
    printf("%d\n", dp[N][V]);

    return 0;
}

一维 dp

#include <stdio.h>

#define MAXSIZE 1010
#define max(a,b) ((a)>(b)?(a):(b))
int N, V, v[MAXSIZE], w[MAXSIZE], dp[MAXSIZE];

void init() {
    scanf("%d%d", &N, &V);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d", v+i, w+i);
    }
}

int main() {
    init();

    for (int i = 1; i <= N; ++i) {
        for (int j = V; j >= v[i]; --j) {
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    printf("%d\n", dp[V]);

    return 0;
}

在线计算

#include <stdio.h>

#define MAXSIZE 1010
#define max(a,b) ((a)>(b)?(a):(b))
int N, V, dp[MAXSIZE];

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

    int vi, wi;
    for (int i = 0; i < N; ++i) {
        scanf("%d%d", &vi, &wi);
        for (int v = V; v >= vi; --v) {
            dp[v] = max(dp[v], dp[v-vi]+wi);
        }
    }
    printf("%d\n", dp[V]);

    return 0;
}