c语言栈解决背包问题求解|递归回溯思路与代码示例

作者：袖梨 2026-09-09

在前端开发内容学习中，c语言栈解决背包问题求解 | 递归回溯思路与代码示例是常见主题。很多人在阅读时会遇到概念分散、步骤不清和注意点难以归纳的问题。本文按照基础概念、操作流程和关键细节，对相关内容进行整理。

c语言栈解决背包问题求解，容易让人联想到完全背包、多重背包等更广的题型，但本文只演示0/1背包的栈模拟回溯写法。也就是说，下面的状态设计、分支展开和示例代码，目标都是解决“每个物品最多取一次”的背包输入，帮助你把递归回溯改写成非递归版本。

问题本质与适用场景

背包问题常见写法是递归或动态规划。如果题目规模不大，又希望完整保留搜索过程、方便输出选择路径，使用栈模拟深度优先搜索是很直接的办法。

这里说的栈解法，本质上是把递归函数中的现场信息改为手动维护。每个状态至少要记录当前处理到第几个物品、当前重量、当前价值，以及下一步该扩展哪条分支。本文后续内容都只对应0/1背包，不直接覆盖完全背包、多重背包等变体。

用栈求解时要保存哪些状态

想把递归改成栈，先要把一次函数调用里真正需要的数据拆出来。只要状态定义完整，压栈和出栈就能稳定复现递归搜索过程。

对0/1背包，最常用的状态是物品下标、当前总重量、当前总价值。若还要回溯当前选择结果，就再保存一个选择数组，或者在状态里保存每一步是否选择该物品。

idx 表示当前处理到的物品位置。
weight 表示已选物品的总重量。
value 表示已选物品的总价值。
choose[] 记录当前路径中每个物品是否被选中。

栈模拟搜索的核心流程

实际遍历时，可以把初始状态先压栈。每次弹出一个状态后，判断是否已经处理完全部物品；如果是，就拿它更新当前最优解。

如果还没处理完，就按不选当前物品和选当前物品两种情况扩展。由于栈是后进先出，通常会先压不选分支，再压可行的选中分支，这样弹栈时会先处理选中路径，调试时更直观。

当 idx 等于物品总数时，比较当前 value 与 bestValue。
扩展选中分支前，要先判断 weight + w[idx] 是否超过背包容量。
若需要输出最优方案，更新最优值时同时复制当前 choose[]。

完整示例代码

下面的示例使用手动栈求解0/1背包，并封装成 solveKnapsack 函数。main 函数支持读入 n、capacity、weights、values，这样就不只是写死样例，而是可以直接求解一组实际输入。

完整示例

#include <stdio.h>
#include <string.h>

#define MAX_N 20
#define MAX_STACK 10000

typedef struct {
    int idx;
    int weight;
    int value;
    int choose[MAX_N];
} State;

void solveKnapsack(int n, int capacity, const int w[], const int v[], int bestChoose[], int *bestValue, int *bestWeight) {
    State stack[MAX_STACK];
    int top = -1;

    State init;
    init.idx = 0;
    init.weight = 0;
    init.value = 0;
    memset(init.choose, 0, sizeof(init.choose));
    stack[++top] = init;

    *bestValue = 0;
    *bestWeight = 0;
    memset(bestChoose, 0, sizeof(int) * n);

    while (top >= 0) {
        State cur = stack[top--];

        if (cur.idx == n) {
            if (cur.value > *bestValue) {
                *bestValue = cur.value;
                *bestWeight = cur.weight;
                memcpy(bestChoose, cur.choose, sizeof(int) * n);
            }
            continue;
        }

        State notTake = cur;
        notTake.idx = cur.idx + 1;
        notTake.choose[cur.idx] = 0;
        stack[++top] = notTake;

        if (cur.weight + w[cur.idx] <= capacity) {
            State take = cur;
            take.idx = cur.idx + 1;
            take.weight = cur.weight + w[cur.idx];
            take.value = cur.value + v[cur.idx];
            take.choose[cur.idx] = 1;
            stack[++top] = take;
        }
    }
}

int main(void) {
    int n, capacity;
    int w[MAX_N], v[MAX_N];
    int bestChoose[MAX_N] = {0};
    int bestValue, bestWeight;

    if (scanf("%d%d", &n, &capacity) != 2) {
        return 1;
    }

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

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

    solveKnapsack(n, capacity, w, v, bestChoose, &bestValue, &bestWeight);

    printf("最大价值: %dn", bestValue);
    printf("最优总重量: %dn", bestWeight);
    printf("选择的物品下标: " );
    for (int i = 0; i < n; i++) {
        if (bestChoose[i]) {
            printf("%d ", i);
        }
    }
    printf("n");

    return 0;
}