用C语言借助栈和回溯法实现背包问题

希望各位大佬能够程序写简单点，本人刚入门，谢谢。

参考GPT和自己的思路：

好的，针对你的问题，我可以给你提供以下的帮助：

首先，背包问题是一个经典的动态规划问题，可以用基本的动态规划算法来解决。不过，你想要用栈和回溯法解决背包问题，也是可行的。下面是一个简单的C语言程序，借助栈和回溯法实现背包问题：

#define MAX 100
typedef struct {
    int w; // 物品重量
    int v; // 物品价值
} Item;

int n; // 物品数量
int W; // 背包容量
int max_value = 0; // 最大价值
Item items[MAX]; // 物品数组
int stack[MAX]; // 栈数组
int top = -1; // 栈顶指针

// 计算是否可行解
int feasible(int weight_so_far, int k) {
    int r = 0;
    if (weight_so_far > W) r = 1; // 超出背包容量，返回0
    else if (k >= n) r = 2; // 所有物品都已考虑，返回1
    else if (weight_so_far + items[k].w <= W) r = 3; // 加入第k个物品后仍未超出背包容量，返回2
    return r;
}

// 回溯算法主体
void backtrack(int weight_so_far, int value_so_far, int k) {
    if (k == n) {
        if (value_so_far > max_value) max_value = value_so_far;
        return;
    }

    // 不选第k个物品
    backtrack(weight_so_far, value_so_far, k+1);

    // 选第k个物品
    int f = feasible(weight_so_far, k);
    if (f == 3) {
        stack[++top] = k;
        backtrack(weight_so_far + items[k].w, value_so_far + items[k].v, k+1);
        top--;
    } else if (f == 1) return;
}

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

    backtrack(0, 0, 0);

    printf("最大价值为：%d\n", max_value);

    return 0;
}

这个程序的思路依然是回溯法，不过用了栈来保存已经选择的物品，当回溯回到根时，把栈中的物品加起来，得到的就是一个可行的解。