当前位置：首页 > news >正文

【数据结构与算法】动态规划

news 2026/6/24 2:37:14

很多人学背包问题时有一个共同困惑：代码能背下来，模板也记住了，但换个题就不会了

这说明你没有真正理解“背包问题”，只是记住了“写法”。

这篇文章的目标不是让你记住代码，而是让你做到：

看到题 → 自己能推状态 → 自己能写转移

一、先别急着学公式，先搞清楚本质

我们从最原始的问题开始：

有一些物品，每个物品有重量和价值，你有一个容量有限的背包，怎么选才能价值最大？

如果不用动态规划，你会怎么做？

方法一：暴力枚举

每个物品有两种选择：

选
不选

n 个物品 → 一共 2ⁿ 种情况

你可以写递归：

int dfs(int i, int remain){ if(i == n) return 0; // 不选 int res = dfs(i+1, remain); // 选（前提：放得下） if(remain >= w[i]){ res = max(res, dfs(i+1, remain - w[i]) + v[i]); } return res; }

这个思路是对的，但复杂度是指数级。

二、为什么需要动态规划

来看这个递归：

dfs(i, remain)

你会发现：

同一个(i, remain)会被计算很多次
这就是“重复子问题”

于是我们想到：

能不能把这些结果存起来？

这就是 DP 的来源。

三、关键一步：状态怎么定义

很多人卡死在这一步。

我们回到递归函数：

dfs(i, remain)

直接把它“翻译”成 DP：

dp[i][j] = 从第 i 个物品开始，在剩余容量 j 下的最大价值

或者更常见的写法：

dp[i][j] = 前 i 个物品，在容量 j 下的最大价值

两种写法本质一样，只是方向不同。

四、状态转移是怎么“想出来”的

现在我们站在 dp[i][j] 这个状态上：

意思是：

我现在有前 i 个物品，背包容量是 j

那第 i 个物品怎么办？

只有两种选择：

1. 不选第 i 个物品

那价值就是：

dp[i-1][j]

2. 选第 i 个物品（前提：j >= w[i]）

那你要腾出空间：

dp[i-1][j - w[i]] + v[i]

合并

dp[i][j] = max(不选, 选)

也就是：

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

注意，这一步不是背出来的，是“分析出来的”。

五、完整代码（二维 DP）

#include<iostream> #include<vector> using namespace std; int main(){ int n, W; cin >> n >> W; vector<int> w(n+1), v(n+1); for(int i=1;i<=n;i++){ cin >> w[i] >> v[i]; } vector<vector<int>> dp(n+1, vector<int>(W+1, 0)); for(int i=1;i<=n;i++){ for(int j=0;j<=W;j++){ // 不选 dp[i][j] = dp[i-1][j]; // 选 if(j >= w[i]){ dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i]); } } } cout << dp[n][W]; }

六、最容易被忽略但最重要的一步：优化

很多人学到这里就结束了，但真正面试中常用的是一维优化。

为什么可以优化？

你看：

dp[i][j] 只依赖 dp[i-1][...]

说明：

我们不需要存整张表，只需要上一行

优化成一维

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

为什么一定要倒序？

这是很多人最容易写错的地方。

如果你正序：

for(j=w[i]; j<=W; j++)

那么：

dp[j-w[i]] 已经被更新过了
相当于同一个物品被选了多次

这就变成了完全背包

七、完全背包：区别到底在哪？

问题变成：

每个物品可以选无限次

转移区别

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

但这次：

for(int j=w[i]; j<=W; j++) // 正序

为什么正序？

因为：

我希望 dp[j-w[i]] 是“当前轮更新过的”

这样才能重复使用物品。

八、你必须搞懂的核心区别（非常重要）

类型	是否可重复	遍历方向
01背包	不可重复	倒序
完全背包	可重复	正序

如果你只记住这一点，已经能做 80% 背包题。

九、再讲一个实战题（真的常考）

题目：分割等和子集

能不能把数组分成两个和相等的部分？

转化

如果总和是 sum：

能不能选一些数，使和 = sum / 2

这就是 01 背包

定义：

dp[j] = 是否能凑出 j

代码

#include<iostream> #include<vector> using namespace std; int main(){ int n; cin >> n; vector<int> nums(n); int sum = 0; for(int i=0;i<n;i++){ cin>>nums[i]; sum += nums[i]; } if(sum % 2){ cout << 0; return 0; } int target = sum / 2; vector<bool> dp(target+1, false); dp[0] = true; for(int i=0;i<n;i++){ for(int j=target;j>=nums[i];j--){ dp[j] = dp[j] || dp[j - nums[i]]; } } cout << dp[target]; }