c语言01背包问题动态规划算法：状态转移与代码示例

在前端开发内容学习中，c语言01背包问题动态规划算法：状态转移与代码示例是常见主题。很多人在阅读时会遇到概念分散、步骤不清和注意点难以归纳的问题。本文按照基础概念、操作流程和关键细节，对相关内容进行整理。

c语言01背包问题动态规划算法的核心，在于把选与不选的决策转成可重复计算的状态转移。本文结合思路拆解、公式说明和完整代码示例，帮助你快速理解实现方法与调试重点。

什么是01背包问题

01背包问题指的是有若干件物品，每件物品只能选一次或不选，在背包容量有限的前提下，要求总价值最大。它是动态规划中的经典入门模型。

题目通常会给出每件物品的重量和价值，再给出背包总容量。求解重点不是枚举所有组合，而是找到一个能重复利用中间结果的状态表示方法。

动态规划算法为什么适合求解

01背包问题同时具备最优子结构和重复子问题两个特征。某一阶段的最优结果，可以由更小规模子问题的最优结果推导出来，所以适合使用动态规划。

常见定义是用dp[i][j]表示前i件物品在容量为j时的最大价值。遇到第i件物品时，要么不选它，要么在容量允许时选它，再比较两种结果的较大值。

• 状态定义：dp[i][j]表示前i件物品放入容量为j的背包后可得到的最大价值。
• 转移思路：如果第i件物品重量大于j，就不能选；否则比较“不选”和“选它一次”两种情况。
• 状态转移公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。

c语言实现思路与完整代码

写代码时，先读入物品数量和背包容量，再分别保存每件物品的重量与价值。之后按照物品和容量两层循环，逐步填满动态规划表。

如果只是学习原理，二维数组写法最直观，便于观察每一步状态变化。等公式理解清楚后，再考虑用一维数组做空间优化。

这里最关键的三句是：先写dp[i][j] = dp[i - 1][j]，表示不选第i件物品，当前容量j时先继承上一行结果；再判断if (j >= w[i])，表示只有背包剩余容量足够时，当前物品才有资格加入；

最后比较dp[i - 1][j - w[i]] + v[i]，表示选择第i件物品后，总价值等于“前i-1件物品在剩余容量j-w[i]下的最优值”加上当前物品价值。

之所以必须从上一行dp[i - 1]转移，是因为01背包中每件物品只能使用一次。若直接从当前行dp[i][j - w[i]]转移，就可能在同一轮里重复使用第i件物品，结果会变成完全背包的含义。

• 完整示例

  #include <stdio.h>
  
  #define MAXN 105
  #define MAXW 1005
  
  int max(int a, int b) {
      return a > b ? a : b;
  }
  
  int main() {
      int n, capacity;
      int w[MAXN], v[MAXN];
      int dp[MAXN][MAXW] = {0};
  
      scanf("%d %d", &n, &capacity);
      for (int i = 1; i <= n; i++) {
          scanf("%d %d", &w[i], &v[i]);
      }
  
      for (int i = 1; i <= n; i++) {
          for (int j = 0; j <= capacity; j++) {
              dp[i][j] = dp[i - 1][j];
              if (j >= w[i]) {
                  dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
              }
          }
      }
  
      printf("%dn", dp[n][capacity]);
      return 0;
  }

• 编译命令：gcc knapsack.c -o knapsack
• 运行命令：./knapsack

样例输入输出与状态转移怎么验证

只看代码还不够，最好用一组标准样例验证结果是否正确。下面这组数据中，3件物品的重量和价值分别为(2,3)、(3,4)、(4,5)，背包容量为5。最优选择是前两件物品，总重量2+3=5，总价值3+4=7。

如果把这个样例输入程序，输出应为7。这样就能直接检查代码是否跑通，也能验证状态转移公式有没有写错。再看一个更小的过程：当处理到第2件物品、容量j=5时，不选它的价值是dp[1][5]=3；选它的价值是dp[1][2]+4=3+4=7，所以dp[2][5]最终取7。这个比较过程正好对应“不选当前物品”和“选择当前物品”两种决策。

• 样例输入

  3 5
  2 3
  3 4
  4 5

• 预期输出

  7

• 结果解释：容量为5时，选择第1件和第2件物品比单独选择第3件物品更优，所以最大价值是7。
• 小样例看状态变化：dp[2][5]要比较dp[1][5]和dp[1][5-3]+4，也就是比较3和7，最终取7。
• 为什么不能从当前行转移：若误写成dp[i][j-w[i]] + v[i]，第2件物品可能在同一行被重复累加，违反“每件物品只能选一次”的题意。

调试时要重点检查哪些地方

很多人代码写出来后结果不对，常见原因不是公式错，而是数组下标、循环范围或输入顺序处理有误。尤其是i从1开始还是从0开始，要和状态定义保持一致。

调试时不要只记原则，更要把“问题现象 -> 可能原因 -> 检查方法”连起来排查。这样一旦输出异常，就能更快定位到具体代码位置。

• 现象：输出结果明显偏小。可能原因：j >= w[i]条件写错、读取重量和价值的顺序写反、可选分支没有参与max比较。检查方法：先用文中的3件物品样例逐步打印dp[i][j]，确认dp[2][5]是否能得到7。
• 现象：输出结果异常偏大。可能原因：把二维转移误写成当前行来源，或一维优化时容量循环写成顺序，导致同一件物品被重复使用。检查方法：重点看转移是否来自dp[i - 1][...]，以及一维写法是否从capacity倒序循环。
• 现象：程序崩溃或输出随机值。可能原因：数组越界，例如n超过MAXN-1，或capacity超过MAXW-1。检查方法：输入前先确认题目数据范围，必要时增大宏定义，避免访问dp[MAXN][MAXW]之外的空间。
• 现象：边界样例不对，比如容量为0时仍有非零结果。可能原因：dp初值没有清零，或循环起点、终点写错。检查方法：确认int dp[MAXN][MAXW] = {0};保留不变，并检查j是否从0开始遍历。
• 现象：编译能过，但运行结果一直不符合预期。可能原因：题目要求输入格式是“重量 价值”，而代码按“价值 重量”读取。检查方法：对照题面重新核对scanf("%d %d", &w[i], &v[i])中的变量顺序。

如何理解样例与实际应用

学习01背包问题时，建议先手算一个只有三到四件物品的小样例，再对照代码中的dp表变化。这样更容易看懂“选或不选”为什么会形成状态转移。

这类算法常用于资源分配、预算选择、容量受限装载等场景。虽然题目形式不同，但只要符合“每件物品只能取一次”和“总容量有限”这两个条件，就可以往01背包模型上靠。

时间复杂度与空间复杂度怎么看

二维动态规划写法需要两层循环遍历物品和容量，所以时间复杂度是O(n*capacity)。如果保留完整的dp表，空间复杂度也是O(n*capacity)。这种写法的优点是结构清晰，便于初学者观察每一行状态如何得到。

如果改成一维优化，时间复杂度仍然是O(n*capacity)，因为状态总数没有减少；但空间复杂度可以降到O(capacity)。二维写法适合理解转移过程和调试，一维写法更适合数据范围较大、内存要求更严格的题目，不过一定要记住容量必须倒序遍历。

• 二维写法：时间复杂度O(n*capacity)，空间复杂度O(n*capacity)，更适合教学和打印状态表。
• 一维优化：时间复杂度不变，空间复杂度降为O(capacity)，更适合正式做题时节省内存。