c++ 动态规划背包问题 c++ dp算法入门教程

0-1背包问题通过动态规划求解，定义dpi为前i个物品在容量j下的最大价值，转移方程为dpi=max(dpi-1, dpi-1]+v[i-1])，初始状态dp0=0；可用二维数组实现，也可优化为一维数组，从后往前遍历避免覆盖；该思想扩展至完全背包、多重背包等问题。

动态规划（Dynamic Programming，简称 DP）是算法中非常重要的思想，尤其在解决最优化问题时非常有效。背包问题是学习 DP 的经典入门题，帮助理解状态定义、转移方程和边界处理。本文以 0-1 背包为例，带你用 C++ 快速掌握 DP 基础。

什么是 0-1 背包问题？

你有一个容量为 V 的背包，和 n 个物品。每个物品有重量 w[i] 和价值 v[i]。每件物品只能选或不选（即“0 或 1”），目标是让装入背包的物品总价值最大。

输入示例：
n = 4, V = 8
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]

输出：10（选第1、2、4个物品，总重 2+3+5=10？不对，超了。正确组合是第2和第4：3+5=8，价值 4+6=10）

DP 状态设计与转移方程

我们定义：
dp[i][j] 表示前 i 个物品中，背包容量为 j 时能获得的最大价值。

立即学习“C++免费学习笔记（深入）”；

对于第 i 个物品（下标从 1 开始），有两种选择：

• 不选：dp[i][j] = dp[i-1][j]
• 选（前提是 j ≥ w[i-1]）：dp[i][j] = dp[i-1][j - w[i-1]] + v[i-1]

所以转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])

初始条件：dp[0][j] = 0（没有物品，价值为0）

ChartGen

AI快速生成专业数据图表

下载

C++ 实现代码（二维数组版本）

这是最容易理解的写法：

#include 
#include 
#include 
using namespace std;
int main() {
int n, V;
cin >> n >> V;
vector w(n), v(n);
for (int i = 0; i < n; i++) {
cin >> w[i] >> v[i];
}
vector> dp(n + 1, vector(V + 1, 0));

for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= V; j++) {
        dp[i][j] = dp[i-1][j]; // 不选
        if (j >= w[i-1]) {
            dp[i][j] = max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]);
        }
    }
}

cout << dp[n][V] << endl;
return 0;
}

空间优化：一维数组滚动
观察发现：每次只依赖上一行的数据。可以将空间从 O(nV) 降到 O(V)。
关键点：内层循环要从后往前遍历，避免覆盖还未计算的状态。
vector dp(V + 1, 0);
for (int i = 0; i < n; i++) {
    for (int j = V; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}
cout << dp[V] << endl;
这个版本更简洁，是竞赛常用写法。
常见变种与扩展


完全背包：每种物品可选无限次。只需改变内层循环方向：从前往后遍历 j。

多重背包：每种物品最多选 m[i] 次。可通过二进制拆分优化成 0-1 背包。

分组背包：每组选一个，枚举组 → 枚举容量 → 枚举组内物品。

掌握 0-1 背包，就掌握了 DP 的核心思维方式：拆解问题、定义状态、找出转移关系。
基本上就这些。多写几遍代码，自己推一遍状态转移，很快就能上手。