动态规划0-1背包问题c

好的，关于动态规划0-1背包问题的C语言实现，可以参考以下代码：

#include <stdio.h>
#define MAX_N 100
#define MAX_W 1000

int n, W;
int w[MAX_N], v[MAX_N];
int dp[MAX_N+1][MAX_W+1];

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

int main() {
    scanf("%d %d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    for (int i = n-1; i >= 0; i--) {
        for (int j = 0; j <= W; j++) {
            if (j < w[i]) {
                dp[i][j] = dp[i+1][j];            } else {
                dp[i][j] = max(dp[i+1][j], dp[i+1][j-w[i]] + v[i]);
            }
        }
    }

    printf("%d\n", dp[0][W]);

    return 0;
}

相关问题

动态规划法0-1背包问题c语言

下面是使用动态规划法解决 0-1 背包问题的 C 语言代码。其中，items[] 数组存储物品的重量和价值，weight[] 和 value[] 数组分别存储背包容量和价值。

#include <stdio.h>

#define MAX_WEIGHT 100      // 背包最大容量
#define MAX_ITEMS 100       // 物品最大数量

int weight[MAX_ITEMS+1];    // 物品重量
int value[MAX_ITEMS+1];     // 物品价值
int dp[MAX_ITEMS+1][MAX_WEIGHT+1];   // 动态规划数组

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

int main() {
    int n;  // 物品数量
    int w;  // 背包容量

    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &w);

    printf("请输入每个物品的重量和价值：\n");
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &weight[i], &value[i]);
    }

    // 动态规划
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j < weight[i]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
        }
    }

    printf("最大价值为：%d\n", dp[n][w]);

    return 0;
}

在上面的代码中，使用二维数组 dp[i][j] 存储前 i 个物品，容量为 j 时的最大价值。在动态规划过程中，如果当前物品的重量大于当前背包容量，那么最大价值就是前 i-1 个物品，容量为 j 时的最大价值。否则，最大价值就是前 i-1 个物品，容量为 j 时的最大价值和前 i-1 个物品，容量为 j-weight[i] 时的最大价值加上当前物品的价值中的较大值。最终，dp[n][w] 就是最大价值。

用动态规划实现0-1背包问题c语言

下面是使用动态规划实现0-1背包问题的C语言代码：

#include<stdio.h>

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

int knapSack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1];

    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];
        }
    }

    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("Maximum value that can be obtained is %d\n", knapSack(W, wt, val, n));

    return 0;
}

在上面的代码中，我们使用一个二维数组K来存储已经计算过的值。K[i][w]表示在前i个物品中，当背包容量为w时的最大价值。我们通过填充这个数组来得到最终的结果。时间复杂度为O(nW)，其中n是物品数量，W是背包容量。