C语言01背包问题怎么理解？状态转移公式与代码示例

时间：2026-08-14 14:51

c语言01背包问题是动态规划里的经典入门题，也是许多算法题中非常常见的模型。核心关键在于先明确每件物品只能取0次或1次，再通过状态转移计算最大价值。本文将用更容易理解的方式讲清楚01背包的建模思路、C语言代码写法以及常见错误。什么是01背包问题01背包问题的标准描述通常是：有若干件物品，每件物品都对

c语言01背包问题是动态规划里的经典入门题，也是许多算法题中非常常见的模型。核心关键在于先明确每件物品只能取0次或1次，再通过状态转移计算最大价值。本文将用更容易理解的方式讲清楚01背包的建模思路、C语言代码写法以及常见错误。

什么是01背包问题

01背包问题的标准描述通常是：有若干件物品，每件物品都对应重量和价值，背包容量固定，要求在总重量不超过背包容量的前提下，让物品总价值尽可能大。这里的“01”表示每件物品只有两种选择：选一次或者不选，不能重复拿。

这类动态规划题表面上像是在枚举所有选择方案，但如果直接暴力搜索，数据规模一大，运行效率就会明显下降。动态规划的意义就在于保存已经计算过的中间结果，避免重复计算，从而用更稳定的时间复杂度求出最优解。

状态怎么定义才容易写代码

在写c语言01背包问题时，最重要的一步就是先把状态定义清楚。最常见、也最适合初学者理解的定义是：dp[i][j] 表示前 i 件物品在背包容量为 j 时能够取得的最大价值。这样每加入一件新物品时，只需要比较“选它”和“不选它”两种情况。

如果第 i 件物品重量为 w，价值为 v，那么当 j 小于 w 时，说明当前容量装不下这件物品，结果只能沿用上一行；当 j 大于等于 w 时，就比较 dp[i-1][j] 和 dp[i-1][j-w]+v，取较大值即可。这就是01背包问题最核心的状态转移公式。

如果你觉得这个公式比较抽象，可以先手动推一个简单样例。假设只看前 3 件物品，重量分别是 1、2、3，价值分别是 2、4、4，背包容量先看 0 到 5。

先处理第 1 件物品（重 1，值 2）：当容量 j=0 时装不下，所以 dp[1][0]=0；当 j=1 时，可以选择它，因此 dp[1][1]=2；容量 j=2、3、4、5 时，因为当前只有这一件物品可选，所以最大价值仍然都是 2。

再处理第 2 件物品（重 2，值 4）：例如 j=2 时，不选第 2 件是 dp[1][2]=2，选第 2 件是 dp[1][0]+4=4，所以 dp[2][2]=4；j=3 时，不选是 dp[1][3]=2，选是 dp[1][1]+4=6，因此 dp[2][3]=6，这里实际上就是把第 1 件和第 2 件一起装进背包；

j=5 时，不选是 2，选是 dp[1][3]+4=6，所以 dp[2][5]=6。

接着处理第 3 件物品（重 3，值 4）：例如 j=3 时，不选第 3 件是 dp[2][3]=6，选第 3 件是 dp[2][0]+4=4，所以 dp[3][3] 仍然取 6，说明容量为 3 时，前两件物品的组合更划算；j=4 时，不选是 dp[2][4]=6，选是 dp[2][1]+4=6，两种方案一样优；

j=5 时，不选是 dp[2][5]=6，选是 dp[2][2]+4=8，所以 dp[3][5]=8。通过这一步就能看出来，“前几件物品的最优结果”再加上当前物品，正是状态转移的真正含义。

这样手推几格之后，你会发现 dp[i][j] 并不是需要死记硬背的表格，而是在每一个容量位置上都认真比较一次“当前物品要不要选”的结果。

dp[i][j] 的含义必须始终保持一致，不能一会儿表示容量，一会儿又表示价值。
状态转移时一定要参考上一件物品的结果，这正是“每件物品只能使用一次”的关键。
如果题目要求的是最大价值，初始化通常以 0 为主；如果遇到恰好装满等特殊变形，初始化方式就需要单独处理。

C语言完整实现示例

对于初学者来说，先写二维数组版本会更容易理解，因为它与状态定义一一对应，调试时也更方便观察每一层状态的变化。等你真正理解状态转移过程之后，再考虑压缩成一维数组进行空间优化。

下面的示例使用固定数组演示01背包标准写法，适合用来理解输入数据、状态初始化、双重循环和最终输出之间的关系。

这段程序的样例数据是：4 件物品，背包容量 5，物品信息分别是 (1,2)、(2,4)、(3,4)、(4,5)，括号中表示“重量,价值”。程序最后输出的是 8，表示在容量不超过 5 的条件下，能够得到的最大总价值为 8。

为什么最终答案是 8？因为最优选择是第 1 件和第 4 件，或者第 2 件和第 3 件。前一种方案总重量 1+4=5，总价值 2+5=7；后一种方案总重量 2+3=5，总价值 4+4=8，因此真正的最优解是选择第 2 件和第 3 件。

如果从状态转移的角度来看，最后一格 dp[4][5] 会比较两种情况：不选第 4 件时，值是 dp[3][5]=8；选第 4 件时，值是 dp[3][1]+5=2+5=7。因为 8 大于 7，所以最终保留 8。

这也说明代码最后输出 dp[n][capacity] 并不是“直接得到答案”，而是前面每一格不断比较、不断更新后累积出来的最优结果。

完整示例

#include 

int main(void) {
    int n = 4;
    int capacity = 5;
    int weight[5] = {0, 1, 2, 3, 4};
    int value[5] = {0, 2, 4, 4, 5};
    int dp[5][6] = {0};

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= capacity; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weight[i]) {
                int candidate = dp[i - 1][j - weight[i]] + value[i];
                if (candidate > dp[i][j]) {
                    dp[i][j] = candidate;
                }
            }
        }
    }

    printf("%dn", dp[n][capacity]);
    return 0;
}