c++ 动态规划背包问题 c++ dp算法入门教程_石家庄创泽智能科技有限公司

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-26

浏览次数：次

返回列表

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

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

动态规划（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 时能获得的最大价值。

对于第 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）

Motiff妙多

Motiff妙多是一款AI驱动的界面设计工具，定位为“AI时代设计工具”

334 查看详情 Motiff妙多

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

这是最容易理解的写法：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int main() {
int n, V;
cin >> n >> V;
vector<int> w(n), v(n);
for (int i = 0; i < n; i++) {
cin >> w[i] >> v[i];
}</p><pre class="brush:php;toolbar:false;">vector<vector<int>> dp(n + 1, vector<int>(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<int> 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;

这个版本更简洁，是竞赛常用写法。