递归算法求01背包问题的完整c语言代码

以下是求解01背包问题的完整递归算法C语言代码：

#include <stdio.h> 

// 定义背包容量和物品个数 
#define N 5 
#define C 10 

// 物品重量和价值 
int w[N] = {2, 2, 6, 5, 4}; 
int v[N] = {6, 3, 5, 4, 6}; 

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

// 递归实现01背包问题 
int knapsack(int i, int j) { 
    if (i == N) { // 没有物品可以放置了 
        return 0; 
    } 
    if (j < w[i]) { // 当前物品放不下，尝试放下一个物品 
        return knapsack(i+1, j); 
    } else { // 可以放置该物品，需要比较放置和不放置的价值 
        return max(knapsack(i+1, j), knapsack(i+1,j-w[i]) + v[i]); 
    } 
} 

int main() { 
    int result = knapsack(0, C); 
    printf("01背包问题的最大价值为：%d\n", result); 
    return 0; 
} 

注意：此代码中未进行输入数据的操作，需要自己在代码中进行定义。另外，此代码为递归实现的01背包问题，不是最优解，仅供学习参考。

相关问题

背包问题C语言非递归算法程序

以下是背包问题的 C 语言非递归算法程序：

#include <stdio.h>

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

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

int knapsack(int n, int w[], int v[], int W) {
    int dp[MAX_W + 1] = {0}; // 初始化为 0
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

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

该算法使用动态规划思想，通过填表法求解背包问题，时间复杂度为 $O(nW)$，空间复杂度为 $O(W)$。

使用回溯算法解决背包问题，使用C语言，非递归

好的，下面是使用回溯算法解决背包问题的非递归C语言实现：

#include <stdio.h>

#define MAXN 20

int n, C, max_w; // 物品数量、背包容量、最大总价值
int v[MAXN], w[MAXN]; // 物品体积和价值
int x[MAXN], best[MAXN]; // 当前解和最优解

// 回溯算法求解背包问题
void backtrack() {
    int cur_w = 0, cur_v = 0, i = 1;
    while (i > 0) {
        if (i > n) { // 已经考虑完所有物品
            if (cur_w > max_w) { // 更新最优解
                max_w = cur_w;
                for (int j = 1; j <= n; j++) best[j] = x[j];
            }
            i--; // 回溯
        } else if (cur_v + v[i] <= C) { // 尝试放入第 i 个物品
            x[i] = 1;
            cur_v += v[i];
            cur_w += w[i];
            i++;
        } else { // 不放入第 i 个物品
            x[i] = 0;
            i++;
        }
        while (i <= n && cur_w + (C - cur_v) * w[i] <= max_w) { // 剪枝
            i++;
        }
        if (i <= n && cur_v + v[i] > C) { // 剪枝
            x[i] = 0;
            i++;
        }
        if (i > n) { // 回溯
            i--;
            x[i] = 0;
            cur_v -= v[i];
            cur_w -= w[i];
            i++;
        }
    }
}

int main() {
    printf("请输入物品数量和背包容量：\n");
    scanf("%d %d", &n, &C);
    printf("请输入每个物品的体积和价值：\n");
    for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);

    max_w = 0;
    backtrack();

    printf("最大总价值为：%d\n", max_w);
    printf("选择的物品为：\n");
    for (int i = 1; i <= n; i++) {
        if (best[i]) printf("%d ", i);
    }
    printf("\n");

    return 0;
}

在这个程序中，我们使用了一个 while 循环来模拟递归调用。在循环中，我们首先初始化当前解、当前体积和当前价值，然后开始考虑第一个物品。在循环中，我们分别尝试将第 $i$ 个物品放入背包中和不放入背包中，然后更新当前解、当前体积和当前价值，并更新 $i$ 的值。如果已经考虑完所有物品，我们就更新最优解，并回溯到上一层。在回溯时，我们需要将当前解、当前体积和当前价值恢复到上一次状态。

在程序中，我们使用了两种剪枝策略来提高算法效率。第一种剪枝策略是在每次选择物品时，我们计算剩余物品的最大可能总价值，如果这个总价值已经小于当前最优解，就可以直接回溯。第二种剪枝策略是在选择完一个物品后，如果当前背包已经超过容量，就直接回溯。这两种剪枝策略可以减少搜索的时间，提高算法效率。

需要注意的是，非递归实现的代码比递归实现的代码更加复杂，但是能够避免递归调用带来的额外开销和栈溢出等问题，因此在一些场景下更加实用。