C

二维朴素 dp

状态转移方程为

$$ f(i, j) = \max_\limits{kv_i \leqslant j \leqslant V} \lbrace f(i-1, j-kv_i) + kw_i\rbrace,\quad i, j, k \in \mathbb{N}. $$

#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) {
            for (int k = 0; k*v[i] <= j; ++k) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    printf("%d\n", dp[N][V]);

    return 0;
}

二维优化 dp

由上有
$$ f(i, j) = \max \lbrace f(i-1, j), f(i-1, j-v_i) + w_i, f(i-1, j-2v_i) + 2w_i, \cdots, f(i-1, j-kv_i) + kw_i \rbrace,\quad kv_i \leqslant j \leqslant V, i, j, k \in \mathbb{N}, $$
则
$$ f(i, j-v_i) = \max \lbrace f(i-1, j-v_i), f(i-1, j-2v_i) + w_i, f(i-1, j-3v_i) + 2w_i, \cdots, f(i-1, j-kv_i) + (k-1)w_i \rbrace,\quad kv_i \leqslant j \leqslant V, i, j, k \in \mathbb{N}, $$
故
$$ f(i, j) = \max \lbrace f(i-1, j), f(i, j-v_i) + w_i \rbrace, \quad v_i \leqslant j \leqslant V,i, j, k \in \mathbb{N}. $$

#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][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[i]; j <= V; ++j) {
            dp[j] = max(dp[j], dp[j-v[i]]+w[i]);
        }
    }
    printf("%d\n", dp[V]);

    return 0;
}