C语言实现0-1背包问题

以下是C语言实现0-1背包问题的代码和解释：

#include <stdio.h>

// 定义最大物品数量和最大容量
#define MAX_N 1000
#define MAX_W 1000

// 物品数量、容量、价值数组
int n, W;
int w[MAX_N], v[MAX_N];

// 记忆化数组
int dp[MAX_N][MAX_W];

// 递归函数
int rec(int i, int j) {
    if (dp[i][j] >= 0) {
        return dp[i][j];
    }
    int res;
    if (i == n) {
        res = 0;
    } else if (j < w[i]) {
        res = rec(i + 1, j);
    } else {
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);    }
    return dp[i][j] = res;
}

int main() {
    // 输入物品数量和容量
    scanf("%d %d", &n, &W);

    // 输入物品的重量和价值
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    // 初始化记忆化数组
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_W; j++) {
            dp[i][j] = -1;
        }
    }

    // 输出结果
    printf("%d\n", rec(0, W));

    return 0;
}

解释：

0-1背包问题是一个经典的动态规划问题，其思路是将问题分解为子问题，逐步求解。具体来说，我们可以定义一个递归函数`rec(i, j)`，表示在前i件物品中选择总重量不超过j的物品的最大价值。然后，我们可以根据递推关系式，从最基本的情况开始逆推，用多重循环讨论所有可能，最后得出答案。

在C语言中，我们可以使用记忆化搜索的方法来实现递归函数。具体来说，我们可以定义一个二维数组`dp`，表示在前i件物品中选择总重量不超过j的物品的最大价值。在递归函数中，我们首先判断`dp[i][j]`是否已经计算过，如果是，则直接返回结果；否则，我们根据递推关系式计算结果，并将结果存入`dp[i][j]`中。