给出这三种方法的代码，用c语言

1. 动态规划解法：

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

#define MAXN 1000
#define MAXM 1000

int w[MAXN], v[MAXN];  // 物品的重量和价值
int dp[MAXN][MAXM];    // dp数组，dp[i][j]表示前i个物品中选择总重量不超过j的物品的最大价值

int max(int a, int b) {
    return a > b ? a : b;
}

int main() {
    int n, m;  // 物品数量和背包容量
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

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

2. 回溯算法解法：

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

#define MAXN 1000
#define MAXM 1000

int w[MAXN], v[MAXN];  // 物品的重量和价值
int max_v = -1;        // 最大价值
int cur_v = 0, cur_w = 0;  // 当前价值和重量

void dfs(int n, int m, int k) {  // k表示当前处理到第k个物品
    if (cur_w > m) {
        return;
    }
    if (k > n) {
        if (cur_v > max_v) {
            max_v = cur_v;
        }
        return;
    }
    dfs(n, m, k+1);  // 不选第k个物品
    cur_v += v[k];
    cur_w += w[k];
    dfs(n, m, k+1);  // 选第k个物品
    cur_v -= v[k];
    cur_w -= w[k];
}

int main() {
    int n, m;  // 物品数量和背包容量
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    dfs(n, m, 1);
    printf("%d\n", max_v);

    return 0;
}

3. 暴力枚举解法：

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

#define MAXN 1000
#define MAXM 1000

int w[MAXN], v[MAXN];  // 物品的重量和价值
int max_v = -1;        // 最大价值

void dfs(int n, int m, int k, int cur_w, int cur_v) {  // cur_w表示当前重量，cur_v表示当前价值
    if (cur_w > m) {
        return;
    }
    if (k > n) {
        if (cur_v > max_v) {
            max_v = cur_v;
        }
        return;
    }
    dfs(n, m, k+1, cur_w, cur_v);             // 不选第k个物品
    dfs(n, m, k+1, cur_w+w[k], cur_v+v[k]);  // 选第k个物品
}

int main() {
    int n, m;  // 物品数量和背包容量
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    dfs(n, m, 1, 0, 0);
    printf("%d\n", max_v);

    return 0;
}