背包问题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$ 的值。如果已经考虑完所有物品，我们就更新最优解，并回溯到上一层。在回溯时，我们需要将当前解、当前体积和当前价值恢复到上一次状态。

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

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

用c语言按以下要求完成代码： 在杂货店中有n 种不同的货物。现将货物装车，规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用w(i) 的空间，价值为p(i) 。现要求设计算法和程序使车中装载的物品价值最大。当然，所装货物不能超过车的容量，且同一种物品不得拿走多件，可自行输入项数值，并对应不同算法给出两个不同的交互界面 （1）给出多种求解算法，如递归算法、非递归算法； （2）编程实现所给算法； （3）对所写算法给出时空复杂性分析。

以下是使用动态规划算法实现0/1背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 100
#define MAX_C 1000

int n, c;
int w[MAX_N], p[MAX_N];
int dp[MAX_N+1][MAX_C+1];

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

int knapsack() {
    int i, j;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= c; 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]]+p[i]);
        }
    }
    return dp[n][c];
}

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

交互界面1：

请输入物品数量和背包容量：
5 10
请输入每个物品的重量和价值：
2 6
2 3
6 5
5 4
4 6
最大价值为：15

交互界面2：

请输入物品数量和背包容量：
4 7
请输入每个物品的重量和价值：
3 4
2 3
4 2
1 1
最大价值为：7

时空复杂度分析：

该算法的时间复杂度为O(nc)，其中n为物品数量，c为背包容量，空间复杂度也为O(nc)。因为在动态规划中需要维护一个二维数组来记录每个状态的最优解，因此空间复杂度较高。