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

作者：袖梨 2026-09-08

在前端开发内容学习中，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])中的变量顺序。