01背包问题c语言代码穷举怎么写

作者：袖梨 2026-09-09

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

01背包问题c语言代码穷举适合用来理解选择与不选择两种分支的搜索过程。本文用清晰的状态定义、完整代码和小样例说明如何从输入、递归到结果输出一步步写对。

先明确01背包穷举在枚举什么

01背包问题的核心是：每件物品只有取与不取两种状态，在总容量不超过限制的前提下，让总价值尽量大。穷举写法不是直接猜答案，而是把每件物品的两种选择都走一遍，再比较最后结果。

用C语言实现时，最重要的是先把状态说清楚。常见状态包括当前处理到第几件物品、已经用了多少容量、当前累计价值是多少。只要这三个量定义稳定，递归过程就不会写乱。

穷举代码的价值不在速度，而在思路直观。它能帮助你看懂01背包为什么能拆成分支搜索，也方便后面再过渡到动态规划版本。这里需要注意，这种写法本质上会枚举每件物品“选”或“不选”的全部情况，时间复杂度通常是O(2^n)。当物品数量很少时，它比较适合学习、调试和验证；但当n变大后，搜索规模会迅速膨胀，这时更适合切换到动态规划等更高效的解法。

每到一件物品，都有“不选它”和“选它”两条分支。
只有在加入当前物品后容量不超限时，才允许进入“选它”的分支。
当所有物品都处理完时，用当前价值更新全局最优解。
穷举更适合小规模数据或学习搜索过程，不适合物品数量很大的输入。

递归函数应该怎样设计

写穷举时，建议把递归函数参数控制在最必要的范围内。最常见的做法是传入当前下标index、当前重量curWeight、当前价值curValue，这样每次递归只需要关心下一件物品如何处理。

递归出口通常是index等于物品总数，也就是所有物品都已经决定完毕。到了这个位置，就比较curValue和当前记录的最大价值maxValue，如果更大就更新答案。

为了避免逻辑重复，先无条件走“不选当前物品”的分支，再判断是否还能放下当前物品；如果能放下，再走“选当前物品”的分支。这个顺序简单，调试时也更容易跟踪。

递归设计要点

参数要能完整描述当前搜索状态，常用的是下标、已用容量、当前价值。
出口条件只负责更新最优值，不要在出口里再做多余判断。
容量判断放在进入“选择分支”之前，避免出现非法状态。

01背包问题c语言代码穷举完整示例

下面这份代码使用固定数组演示最基础的穷举写法。程序会遍历每件物品的选与不选，最后输出最大总价值，适合先跑通思路，再根据需要扩展成从键盘输入数据的版本。

示例中共有4件物品，重量分别为2、1、3、2，价值分别为12、10、20、15，背包容量为5。这个样例的实际最优组合是选择第1、2、4件物品，总重量2+1+2=5，总价值12+10+15=37；而像第1、3件物品的组合虽然总重量也是5，但总价值只有32，所以不是最优解。这样就能先在纸面上验算出正确答案，再对照程序输出。

完整示例

#include <stdio.h>

#define N 4

int weights[N] = {2, 1, 3, 2};
int values[N] = {12, 10, 20, 15};
int capacity = 5;
int maxValue = 0;

void dfs(int index, int curWeight, int curValue) {
    if (index == N) {
        if (curValue > maxValue) {
            maxValue = curValue;
        }
        return;
    }

    dfs(index + 1, curWeight, curValue);

    if (curWeight + weights[index] <= capacity) {
        dfs(index + 1,
            curWeight + weights[index],
            curValue + values[index]);
    }
}

int main(void) {
    dfs(0, 0, 0);
    printf("最大价值：%dn", maxValue);
    return 0;
}