ALGORITHM · 动态规划

背包问题：从零到精通

C 语言与 C++ 实现 · 0/1背包 · 完全背包 · 多重背包

一、什么是背包问题？

背包问题（Knapsack Problem）是组合优化领域最经典的问题之一，也是学习动态规划（Dynamic Programming）的入门首选。

问题描述：给定 n 个物品，每个物品有重量 w[i] 和价值 v[i]，以及一个容量为 W 的背包。选择若干物品装入背包，使得在总重量不超过 W 的前提下，总价值最大。

背包问题的分类

类型

每个物品可选次数

典型问题

0/1 背包

最多选 1 次

投资组合选择

完全背包

无限次

硬币找零

多重背包

有限次 c[i]

仓库库存分配

分组背包

每组选 1 个

课程选择

本文将使用 C 语言和 C++ 分别实现 0/1 背包、完全背包和多重背包三种变体，帮助你全面理解背包问题的核心思想。

二、0/1 背包问题

2.1 问题分析

定义状态 dp[i][j]：考虑前 i 个物品，背包容量为 j 时的最大价值。

状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])    (j >= w[i])

dp[i][j] = dp[i-1][j]                                  (j <  w[i])

2.2 C 语言实现（二维数组）

📝 C 语言 · 0/1 背包 · 二维 DP

#include <stdio.h>

// 定义最大物品数量和背包最大容量
#define MAXN 1005
#define MAXW 10005

// 求两个整数中较大值的宏/函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int n, W;
    int w[MAXN], v[MAXN];
    // dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值
    int dp[MAXN][MAXW] = {0}; 

    // 读取物品数量 n 和背包容量 W
    scanf("%d %d", &n, &W);
    
    // 读取每个物品的重量 w[i] 和价值 v[i]
    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 <= W; j++) {
            if (j >= w[i]) {
                // 如果当前背包容量 j 能够装下第 i 个物品：
                // 比较“不装第 i 个物品”和“装第 i 个物品”两种情况，取最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            } else {
                // 如果当前背包容量 j 装不下第 i 个物品：
                // 最大价值等于前 i-1 个物品在容量 j 下的最大价值
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    // 输出最终结果：前 n 个物品放入容量为 W 的背包的最大价值
    printf("%d\n", dp[n][W]);

    return 0;
}

2.3 C++ 实现（滚动数组优化）

二维数组 dp[i][j] 只依赖上一行 dp[i-1][*]，因此可以用一维数组从后往前更新，空间从 O(nW) 降到 O(W)。

📝 C++ · 0/1 背包 · 一维滚动数组

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max 函数

using namespace std;

int main() {
    int n, W;
    // 读取物品数量 n 和背包总容量 W
    cin >> n >> W;
    
    // 使用 vector 存储物品的重量 w 和价值 v，索引从 1 开始
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    // 初始化为 0，表示没有任何物品时，任何容量的最大价值都是 0
    vector<int> dp(W + 1, 0);

    // 外层循环：遍历每一个物品
    for (int i = 1; i <= n; i++) {
        // 内层循环：逆序遍历背包容量（从最大容量 W 递减到当前物品的重量 w[i]）
        // 逆序遍历是为了保证每个物品最多只被放入背包一次
        for (int j = W; j >= w[i]; j--) {
            // 状态转移方程：
            // 比较“不放入当前物品”和“放入当前物品”两种情况，取最大值
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // 输出最终结果：容量为 W 的背包能装下的最大价值
    cout << dp[W] << endl;

    return 0;
}

⚠️ 关键点：0/1 背包的一维优化必须从后往前遍历 j，否则会重复使用同一个物品（变成完全背包）。

三、完全背包问题

3.1 问题分析

与 0/1 背包的区别：每个物品可以选无限次。状态转移方程变为：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])    (j >= w[i])

注意这里是 dp[i][j-w[i]] 而不是 dp[i-1][j-w[i]]，因为同一物品可以重复选取。一维优化时，只需把内层循环改为正序遍历。

3.2 C 语言实现

📝 C 语言 · 完全背包 · 一维优化

#include <stdio.h>

// 定义最大物品数量和背包最大容量
#define MAXN 1005
#define MAXW 10005

// 求两个整数中较大值的宏/函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int n, W;
    int w[MAXN], v[MAXN];
    
    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    // 初始化为 0，表示没有任何物品时，任何容量的最大价值都是 0
    int dp[MAXW] = {0}; 

    // 读取物品数量 n 和背包总容量 W
    scanf("%d %d", &n, &W);
    
    // 读取每个物品的重量 w[i] 和价值 v[i]
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &w[i], &v[i]);
    }

    // 动态规划状态转移过程
    for (int i = 1; i <= n; i++) {
        // 【核心逻辑】：正序遍历背包容量（从当前物品的重量 w[i] 递增到最大容量 W）
        // 正序遍历保证了在计算 dp[j] 时，dp[j - w[i]] 已经在当前轮次被更新过。
        // 这意味着 dp[j - w[i]] 中可能已经包含了当前物品 i，从而允许同一物品被多次放入背包
        for (int j = w[i]; j <= W; j++) {
            // 状态转移方程：
            // 比较“不放入当前物品”和“放入当前物品”两种情况，取最大值
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // 输出最终结果：容量为 W 的背包能装下的最大价值
    printf("%d\n", dp[W]);

    return 0;
}

3.3 C++ 实现

📝 C++ · 完全背包

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max 函数

using namespace std;

int main() {
    int n, W;
    // 读取物品数量 n 和背包总容量 W
    cin >> n >> W;
    
    // 使用 vector 存储物品的重量 w 和价值 v，索引从 1 开始
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> w[i] >> v[i];
    }

    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    // 初始化为 0，表示没有任何物品时，任何容量的最大价值都是 0
    vector<int> dp(W + 1, 0);

    // 外层循环：遍历每一个物品
    for (int i = 1; i <= n; i++) {
        // 【核心逻辑】：正序遍历背包容量（从当前物品的重量 w[i] 递增到最大容量 W）
        // 正序遍历保证了在计算 dp[j] 时，dp[j - w[i]] 已经在当前轮次被更新过。
        // 这意味着 dp[j - w[i]] 中可能已经包含了当前物品 i，从而允许同一物品被多次放入背包。
        for (int j = w[i]; j <= W; j++) {
            // 状态转移方程：
            // 比较“不放入当前物品”和“放入当前物品”两种情况，取最大值
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    // 输出最终结果：容量为 W 的背包能装下的最大价值
    cout << dp[W] << endl;

    return 0;
}

四、多重背包问题

4.1 问题分析

每个物品有数量上限 c[i]。朴素做法是把每件物品展开成 c[i] 个 0/1 背包物品，复杂度 O(nW * c[i])。

更优的做法是二进制拆分：把 c[i] 拆成 1, 2, 4, ..., 2^k, remainder 份，转化为 O(log c[i]) 个 0/1 背包物品。

4.2 C++ 实现（二进制拆分）

📝 C++ · 多重背包 · 二进制拆分

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max 函数

using namespace std;

// 定义物品结构体，包含重量 w 和价值 v
struct Item { 
    int w, v; 
};

int main() {
    int n, W;
    // 读取物品种类数 n 和背包总容量 W
    cin >> n >> W;
    
    // 用于存储二进制拆分后的新物品
    vector<Item> items;

    for (int i = 0; i < n; i++) {
        int w, v, c;
        // 读取当前物品的重量 w、价值 v 和数量限制 c
        cin >> w >> v >> c;
        
        // 【核心逻辑】：二进制拆分
        // 将数量 c 拆分为 1, 2, 4, ..., 2^k, 剩余量 的组合
        int k = 1;
        while (k <= c) {
            // 将拆分出的组合包作为一个独立的新物品存入数组
            items.push_back({w * k, v * k});
            c -= k;   // 减去已拆分的数量
            k *= 2;   // 翻倍，准备拆分下一个 2 的幂次
        }
        // 如果最后还有剩余数量，将其单独作为一个新物品存入
        if (c > 0) {
            items.push_back({w * c, v * c});
        }
    }

    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    vector<int> dp(W + 1, 0);

    // 将拆分后的物品视为 0/1 背包问题进行求解
    for (auto& it : items) {
        // 【核心逻辑】：逆序遍历背包容量
        // 保证每个“组合包”最多被放入背包一次，符合 0/1 背包的特性
        for (int j = W; j >= it.w; j--) {
            // 状态转移方程：比较“不放入”和“放入当前组合包”两种情况，取最大值
            dp[j] = max(dp[j], dp[j - it.w] + it.v);
        }
    }

    // 输出最终结果：容量为 W 的背包能装下的最大价值
    cout << dp[W] << endl;

    return 0;
}

4.3 C 语言实现（朴素方法）

📝 C 语言 · 多重背包 · 朴素方法

#include <stdio.h>

// 定义背包最大容量
#define MAXW 10005

// 求两个整数中较大值的宏/函数
int max(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    int n, W;
    // 读取物品种类数 n 和背包总容量 W
    scanf("%d %d", &n, &W);

    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    int dp[MAXW] = {0};

    // 外层循环：遍历每一种物品
    for (int i = 0; i < n; i++) {
        int w, v, c;
        // 读取当前物品的重量 w、价值 v 和数量限制 c
        scanf("%d %d %d", &w, &v, &c);

        // 内层循环：逆序遍历背包容量（保证每个物品在本次决策中只被考虑一次）
        for (int j = W; j >= w; j--) {
            // 最内层循环：枚举当前物品选取的数量 k（从 1 到 c，且不能超过当前容量 j）
            for (int k = 1; k <= c && k * w <= j; k++) {
                // 状态转移方程：
                // 比较“不放入更多当前物品”和“放入 k 个当前物品”两种情况，取最大值
                dp[j] = max(dp[j], dp[j - k * w] + k * v);
            }
        }
    }

    // 输出最终结果：容量为 W 的背包能装下的最大价值
    printf("%d\n", dp[W]);

    return 0;
}

五、复杂度对比与选择建议

问题类型

时间复杂度

空间复杂度

优化技巧

0/1 背包

O(nW)

O(W) 滚动数组

逆序遍历 j

完全背包

O(nW)

O(W)

正序遍历 j

多重背包（朴素）

O(nW * c)

O(W)

三重循环

多重背包（二进制拆分）

O(nW * log c)

O(W + n log c)

拆分为 log c 个物品

选择建议：

  • 0/1 背包：逆序遍历 j，空间一维优化即可。
  • 完全背包：正序遍历 j，与 0/1 背包唯一区别。
  • 多重背包：数据量小时朴素可行；数据量大时必须用二进制拆分或单调队列优化。
  • C 语言实现需手动管理数组大小；C++ 使用 vector 更灵活安全。

六、经典例题实战

例题：洛谷 P1048 采药

题目：辰辰有 M 分钟，共有 n 株草药，每株需要时间 t[i] 采摘，价值 v[i]。求最大价值。

这是一道标准的 0/1 背包问题。将 M 视为背包容量，每株草药就是一个物品。

📝 C++ · P1048 采药 · 完整解答

#include <iostream>
#include <vector>
#include <algorithm> // 用于 max 函数

using namespace std;

int main() {
    int M, n;
    // 读取背包总容量 M 和物品数量 n
    cin >> M >> n;
    
    // 使用 vector 存储物品的重量 t 和价值 v，索引从 1 开始
    vector<int> t(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> v[i];
    }

    // 一维滚动数组：dp[j] 表示背包容量为 j 时所能获得的最大价值
    // 初始化为 0，表示没有任何物品时，任何容量的最大价值都是 0
    vector<int> dp(M + 1, 0);

    // 外层循环：遍历每一个物品
    for (int i = 1; i <= n; i++) {
        // 内层循环：逆序遍历背包容量（从最大容量 M 递减到当前物品的重量 t[i]）
        // 逆序遍历是为了保证在计算 dp[j] 时，dp[j - t[i]] 仍然是上一轮（未考虑当前物品）的状态，
        // 从而确保每个物品最多只被放入背包一次。
        for (int j = M; j >= t[i]; j--) {
            // 状态转移方程：
            // 比较“不放入当前物品”和“放入当前物品”两种情况，取最大值
            dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
        }
    }

    // 输出最终结果：容量为 M 的背包能装下的最大价值
    cout << dp[M] << endl;

    return 0;
}

七、常见错误与调试技巧

错误现象

原因

解决方法

答案偏大

0/1 背包正序遍历 j

改为逆序：for(j=W; j>=w[i]; j--)

答案偏小

完全背包逆序遍历 j

改为正序：for(j=w[i]; j<=W; j++)

数组越界

j-w[i] < 0

加条件判断 j >= w[i]

MLE 内存超限

二维数组过大

改用一维滚动数组

TLE 超时

多重背包朴素三重循环

使用二进制拆分或单调队列

八、总结与进阶

背包问题是动态规划的基石，掌握它之后可以触类旁通：

  • 0/1 背包 → 子集和问题、分割等和子集
  • 完全背包 → 零钱兑换、爬楼梯变种
  • 多重背包 → 单调队列优化（P1776）
  • 分组背包 → 依赖背包、树形背包
  • 混合背包 → 组合多种背包类型

建议练习平台：

  • 洛谷（luogu.com.cn）：P1048 采药、P1060 开心的金明、P1776 宝物筛选
  • LeetCode：322 零钱兑换、416 分割等和子集、474 一和零
  • AcWing：2-01背包问题、3-完全背包问题、4-多重背包问题

— END —

感谢阅读，如有疑问欢迎留言交流！

# c语言 # c++ # 开发语言
Logo
AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

cover

WalkingLab 组织入驻 AtomGit，释放高校智能体开源科研成果

avatar AtomGit开源社区
cover

拼手速！GLM-5.2免费Token每天10点准点开抢！

avatar AtomGit开源社区
cover

AtomGit 2026年6月三方库下载量排行榜重磅发布！双榜格局稳固，生态深耕持续发力

avatar AtomGit开源社区