c语言01背包问题怎么理解

作者：袖梨 2026-09-06

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

c语言01背包问题是动态规划中的经典入门题，核心在于明确物品只能取0次或1次，再用状态转移求最大价值。本文用通俗思路说明建模方法、代码写法和常见易错点。

什么是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语言完整实现示例

对入门学习，先写二维数组版本更容易理解，因为它直接对应状态定义，调试时也便于观察每一层的变化。等你完全理解转移过程后，再考虑压缩成一维数组优化空间。

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

这段程序的样例数据是：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 <stdio.h>

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;
}