01背包问题C语言代码

以下是01背包问题的动态规划代码实现，以C语言为例：

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

int knapsack_01(int n, int C, int w[], int v[]) {
    // 定义一个二维数组用于保存状态
    int **dp = (int **)malloc((n+1) * sizeof(int *));
    for (int i = 0; i <= n; i++) {
        dp[i] = (int *)malloc((C+1) * sizeof(int));
    }
    // 初始化状态
    for (int j = 0; j <= C; j++) {
        dp[0][j] = 0;
    }
    // 状态转移
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= C; j++) {
            if (j >= w[i-1]) {
                dp[i][j] = (dp[i-1][j] > dp[i-1][j-w[i-1]]+v[i-1]) ? dp[i-1][j] : dp[i-1][j-w[i-1]]+v[i-1];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    // 返回最终状态
    int res = dp[n][C];
    // 释放动态分配的内存
    for (int i = 0; i <= n; i++) {
        free(dp[i]);
    }
    free(dp);
    return res;
}

int main() {
    int n = 5;
    int C = 10;
    int w[] = {2, 2, 6, 5, 4};
    int v[] = {6, 3, 5, 4, 6};
    int res = knapsack_01(n, C, w, v);
    printf("The maximum value is %d.\n", res);
    return 0;
}

其中，n表示物品数量，C表示背包容量，w和v分别表示物品的重量和价值。在代码中，我们首先动态分配一个n+1行、C+1列的二维数组dp，用于保存状态。然后，我们初始化第0行的状态为0，表示在前0个物品中选择若干个物品放入容量为j的背包中所能获得的最大价值为0。接下来，我们利用状态转移方程，计算出dp[i][j]的值，最后返回dp[n][C]，即在前n个物品中选择若干个物品放入容量为C的背包中所能获得的最大价值。最后，我们释放动态分配的内存。