c语言背包算法怎么实现

作者：袖梨 2026-09-09

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

很多人搜c语言背包算法，真正想解决的通常不是名词解释，而是如何把问题拆成状态、写出转移并在C语言里落地。本文围绕0/1背包讲清建模思路、代码结构和常见易错点。

先弄清背包问题在求什么

背包问题的核心是，在总容量有限的条件下，从若干物品里选择一部分，让总价值尽量大。每件物品通常有两个属性：重量和价值，算法要回答的是怎样选最划算。

如果题目说明每件物品只能取一次，通常就是0/1背包；如果同一种物品可以重复取，通常就是完全背包；如果每种物品只能取有限件数，通常就是多重背包。本文下面给出的状态设计、代码模板、输入输出示例，都是围绕0/1背包展开的。

写C语言程序前，先确认题型，否则循环方向一错，结果就会直接失真。0/1背包一般是容量倒序，完全背包一般是容量正序；多重背包则常见做法是拆分成多个0/1物品，或者再配合其他优化方法处理。

这部分内容的完整代码示例对应的是0/1背包，不是所有背包题都能原样直接套。
如果题目允许同一物品重复选，核心区别通常不在公式本身，而在容量循环方向。
如果题目限制每种物品件数，先看件数和数据范围，再决定是否做二进制拆分。

状态设计和转移怎么写

0/1背包最常见的设计是用dp[j]表示容量恰好或不超过j时能够得到的最大价值。这样做的好处是数组结构简单，C语言实现直接，空间也比二维写法更省。

转移时要枚举每件物品，再判断当前容量j能不能放下它。若能放下，就比较"不选当前物品"和"选当前物品"两种结果，取其中较大值。

一维优化时，容量必须从大到小循环。因为每件物品只能用一次，倒序才能保证本轮更新时读取到的是上一轮物品留下的旧状态，而不是已经被当前物品污染过的新状态。比如处理第i件物品时，dp[j - w[i]]必须表示"前i-1件物品在容量j-w[i]时的最优值"，这样加上v[i]才是合法的"选第i件"方案。

状态定义：dp[j]表示容量为j时的最大总价值。
初始条件：dp数组先全部置为0，表示什么都不选时价值为0。
转移公式：dp[j] = max(dp[j], dp[j - w[i]] + v[i])。
循环顺序：物品在外层，容量j从bag逆序到w[i]。
如果把0/1背包写成容量正序，当前物品会在同一轮被重复利用，结果就偏成完全背包。

C语言完整示例

下面这份代码演示的是标准0/1背包。输入部分给出物品数量、背包容量、每件物品的重量和价值，程序输出最大总价值，适合作为练习和改写模板。

先看这份模板的适用前提：代码里写了MAX_N 105和MAX_W 1005，所以要求n不能超过MAX_N - 1，也就是104；bag不能超过MAX_W - 1，也就是1004。如果题目数据更大，要么把数组上限开大，要么改成动态分配，不能直接照抄。

输入格式也要对齐：第一行输入n和bag；接下来n行，每行输入两个整数，分别表示第i件物品的重量w[i]和价值v[i]。如果你的题目不是从标准输入读取，也可以保留核心循环不动，只替换数据来源。

输入格式：第一行是物品数量n和背包容量bag。
接下来n行：每行两个整数，依次是重量和价值。
适用范围：n <= 104，bag <= 1004。超出这个范围时，这份固定数组模板不能直接使用。

完整示例

#include <stdio.h>

#define MAX_N 105
#define MAX_W 1005

int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int n, bag;
    int w[MAX_N], v[MAX_N];
    int dp[MAX_W] = {0};

    if (scanf("%d %d", &n, &bag) != 2) {
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = bag; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

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