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

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

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

问题本质与适用场景

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

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

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

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

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

1. idx 表示当前处理到的物品位置。
2. weight 表示已选物品的总重量。
3. value 表示已选物品的总价值。
4. 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;
  }

• 编译命令：cc -std=c11 knapsack_stack.c -o knapsack_stack
• 运行命令：./knapsack_stack
• 示例输入：4 8 2 3 4 5 3 4 5 6

结果验证怎么做

只给出代码还不够，最好拿一组固定样例先验算，确认程序真的求出了正确答案。以上面的输入为例，4 个物品的重量分别是 2、3、4、5，价值分别是 3、4、5、6，背包容量是 8。

手工枚举后可以发现，选下标 1 和 3 的物品时，总重量是 3 + 5 = 8，最大价值是 4 + 6 = 10；如果选 0 和 3，总价值只有 9；选 0、1、2 又会超重。所以这组样例的最优解应当是价值 10，对应下标 1 和 3。程序输出和这个结果一致，就说明当前 0/1 背包示例是跑通的。

• 预期最大价值应为 10。
• 预期最优总重量应为 8。
• 预期选择的物品下标应为 1 和 3。

调试与优化时要注意的点

栈写法最常见的问题，不是思路错误，而是状态复制不完整。尤其是选择数组这种路径信息，如果只复制指针、不复制内容，很容易导致多个状态相互污染。

另外，手动栈虽然避开了递归深度限制，但空间仍然会随着搜索树增长。物品很多时，这种方法适合教学、验证和小规模枚举；如果追求大规模效率，还是应优先考虑动态规划。

• 检查压栈前后的 idx、weight、value 是否独立变化。
• 更新最优解时复制当前方案，不要直接共用同一块数组。
• 先用 4 到 6 个物品的小样例验证结果，再扩大输入规模。

如果你要的是看懂搜索过程，或者把递归回溯改写成非递归形式，这种用栈模拟0/1背包搜索的写法很适合练习。先明确本文只解决0/1背包，再把输入、状态、结果验证补完整，整套“求解问题”的过程就更实用了。