c语言代码01背包问题

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

#include <stdio.h>
#define N 5
#define C 10

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

int main() {
    int w[N] = {2, 2, 6, 5, 4}; // 物品重量
    int v[N] = {6, 3, 5, 4, 6}; // 物品价值
    int dp[N + 1][C + 1] = {0}; // 动态规划数组
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= C; j++) {
            if (j >= w[i - 1]) {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    printf("%d\n", dp[N][C]); // 输出最大价值
    return 0;
}

相关问题

01背包问题c语言代码

以下是 01 背包问题的 C 语言代码：

#include <stdio.h>

// 返回两个数中的较大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 01 背包问题函数
int knapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n+1][W+1];

    // 填充 K[][] 数组
    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                K[i][w] = 0;
            }
            else if (wt[i-1] <= w) {
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
            }
            else {
                K[i][w] = K[i-1][w];
            }
        }
    }

    // 返回 01 背包问题的最优解
    return K[n][W];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);

    printf("01 背包问题的最优解为 %d", knapSack(W, wt, val, n));
    return 0;
}

这段代码实现了 01 背包问题的动态规划解法。给定一个背包容量和一组物品的重量和价值，它计算出能够装入背包的最大价值。

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的背包中所能获得的最大价值。最后，我们释放动态分配的内存。