请为我提供一个解决01背包问题的代码

以下是一个解决01背包问题的C语言代码：

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

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 = ; i < n; i++) {
scanf("%d %d", &w[i], &v[i]);
}

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

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

相关问题

用c++写一个解决01背包问题的代码

好的，以下是使用 C 语言解决 01 背包问题的代码：

#include<stdio.h>
#define max_n 1000    // 背包中物品的数量上限
#define max_w 1000    // 背包的最大承重量

int n, W, w[max_n + 5], v[max_n + 5];   // w 代表物品的重量，v 代表物品的价值
int dp[max_w + 5];    // dp[i] 表示背包承重为 i 时的最大价值

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

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

    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= w[i]; j--) {   // 从大到小枚举，避免重复计算
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);    // 状态转移方程
        }
    }

    printf("%d", dp[W]);
    return 0;
}

以上是标准的 01 背包问题的 C 语言解决方案，其中 max_n 和 max_w 分别表示物品数量上限和背包最大承重量，n 和 W 分别表示实际物品数量和背包实际的承重量，w[i] 和 v[i] 分别表示第 i 个物品的重量和价值，dp[i] 表示背包承重为 i 时的最大价值。状态转移方程为 `dp[j] = max(dp[j], dp[j - w[i]] + v[i])`，意思是将前一个状态转移至当前状态，每次取最大值即可。

帮我写一个回溯法解决01背包问题的C语言代码

好的，下面是一个使用回溯法解决01背包问题的C语言代码示例：

#include <stdio.h>
#include <stdbool.h>

#define MAX_N 100 // 物品数量的最大值
#define MAX_W 1000 // 背包容量的最大值

int n; // 物品数量
int w[MAX_N]; // 物品重量
int v[MAX_N]; // 物品价值
int W; // 背包容量
bool used[MAX_N]; // 物品是否已经被选中
int max_v; // 最大价值

// 回溯函数，i为当前考虑的物品编号，cw为当前背包已经装的重量，cv为当前背包的总价值
void backtrack(int i, int cw, int cv) {
    // 如果已经考虑完所有物品，更新最大价值并返回
    if (i == n) {
        if (cv > max_v) {
            max_v = cv;
        }
        return;
    }
    // 不选第i个物品的情况
    backtrack(i + 1, cw, cv);
    // 选第i个物品的情况，需要满足背包容量不超过W，并且第i个物品没有被选择过
    if (cw + w[i] <= W && !used[i]) {
        used[i] = true;
        backtrack(i + 1, cw + w[i], cv + v[i]);
        used[i] = false;
    }
}

int main() {
    // 读入数据
    printf("请输入物品数量和背包容量：");
    scanf("%d %d", &n, &W);
    printf("请输入每个物品的重量和价值：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }
    // 初始化变量
    max_v = 0;
    for (int i = 0; i < n; i++) {
        used[i] = false;
    }
    // 进行回溯
    backtrack(0, 0, 0);
    // 输出结果
    printf("最大价值为：%d\n", max_v);
    return 0;
}

该代码中，backtrack函数表示回溯函数，i表示当前考虑的物品编号，cw表示当前背包已经装的重量，cv表示当前背包的总价值。如果已经考虑完所有物品，就更新最大价值并返回；否则，分别考虑不选第i个物品和选第i个物品的情况，如果选第i个物品，则需要满足背包容量不超过W，并且第i个物品没有被选择过。

在主函数中，首先读入数据，然后进行初始化，最后调用回溯函数进行求解。