企业官网建设流程全解析

👨‍💻 关于作者：会编程的土豆

“不是因为看见希望才坚持，而是坚持了才看见希望。”

你好，我是会编程的土豆，一名热爱后端技术的Java学习者。

📚正在更新中的专栏：

• 《数据结构与算法》😊😊😊

• 《leetcode hot 100》🥰🥰🥰🤩🤩🤩

• 《数据库mysql》

💕作者简介：后端学习者

背包问题是动态规划的经典入门题型，也是面试和算法竞赛中的常客。但对于初学者来说，最困惑的不是状态转移方程，而是：为什么01背包要倒序遍历？为什么完全背包要正序遍历？

本文将用最通俗的语言和图解，帮你彻底理解这两种背包的核心区别。读完这篇文章，你将掌握：

• 01背包与完全背包的标准模板

• 正序与倒序的本质原理

• P1048 采药 和 P1616 疯狂的采药 的 AC 代码

什么是背包问题？

问题描述

有一个容量为m的背包，有n件物品，每件物品有重量w[i]和价值v[i]。问：如何选择物品装入背包，使得总重量不超过容量，且总价值最大？

现实场景

• 旅行打包：行李箱空间有限，怎么装最值钱？

• 投资理财：资金有限，怎么投收益最高？

• 时间管理：时间有限，怎么安排收获最大？

二、01背包（每个物品最多选一次）

经典例题：P1048 [NOIP2005 普及组] 采药

题目大意：有M株草药，每株有采摘时间time和价值value，总时间T内，每株最多采一次，求最大总价值。

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int T, M; cin >> T >> M; vector<int>dp(T + 1, 0); for (int i = 0; i < M; i++) { int time, value; cin >> time >> value; for (int j = T; j >= 0; j--) { if(j>=time) dp[j] = max(dp[j], dp[j - time] + value); } } cout << dp[T] << endl; return 0; }

状态定义

dp[j]表示：在时间不超过j的前提下，能获得的最大价值。

状态转移方程

dp[j] = max(dp[j], dp[j - time] + value)

• dp[j]：不采这株草药

• dp[j - time] + value：采这株草药（花time时间，得value价值）

核心代码

for (int i = 0; i < M; i++) { int time, value; cin >> time >> value; for (int j = T; j >= time; j--) { // 倒序遍历 dp[j] = max(dp[j], dp[j - time] + value); } }

为什么必须倒序？

正序会导致同一物品被多次使用。

举例：T = 3，物品time = 1, value = 10

正序（错误）：

j = 1: dp[1] = max(0, dp[0]+10) = 10 j = 2: dp[2] = max(0, dp[1]+10) = 20 ← 用了刚更新的 dp[1] j = 3: dp[3] = max(0, dp[2]+10) = 30 ← 又用了刚更新的 dp[2]

一个物品被用了3次！

倒序（正确）：

j = 3: dp[3] = max(0, dp[2]+10) = 10 ← dp[2] 还是旧值 0 j = 2: dp[2] = max(0, dp[1]+10) = 10 ← dp[1] 还是旧值 0 j = 1: dp[1] = max(0, dp[0]+10) = 10

每个物品只用了1次。

一句话理解

倒序用"旧值"生"新值"，各容量状态相互隔离，保证物品只用一次。

三、完全背包（每个物品可选无限次）

经典例题：P1616 疯狂的采药

题目大意：与采药相同，但每种草药可以无限次采摘。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int T, M; cin >> T >> M; vector<long long> dp(T + 1, 0); // 注意：可能很大，用 long long for (int i = 0; i < M; i++) { int time, value; cin >> time >> value; // 完全背包：正序遍历 for (int j = time; j <= T; j++) { dp[j] = max(dp[j], dp[j - time] + value); } } cout << dp[T] << endl; return 0; }

核心代码

for (int i = 0; i < M; i++) { int time, value; cin >> time >> value; for (int j = time; j <= T; j++) { // 正序遍历 dp[j] = max(dp[j], dp[j - time] + value); } }

为什么正序就能无限用？

正序让"新值"立刻变成"基础值"供后续使用，形成链式叠加。

举例：T = 3，物品time = 1, value = 10

正序（正确）：

j = 1: dp[1] = max(0, dp[0]+10) = 10 j = 2: dp[2] = max(0, dp[1]+10) = 20 ← 用了刚更新的 dp[1]，叠加一次 j = 3: dp[3] = max(0, dp[2]+10) = 30 ← 用了刚更新的 dp[2]，再叠加一次

物品被用了3次，正是完全背包想要的效果！

一句话理解

正序让"新值生新值"，形成滚雪球效应，允许物品无限次使用。

四、对比总结表

五、变种：不选也有价值（P1802 5倍经验日）

有些题目中，"不选"这个决策也会产生价值。例如 P1802，打不过好友也能获得失败经验。

状态转移

for (int j = x; j >= 0; j--) { long long no_use = dp[j] + lose; // 不打，得失败经验 long long use = (j >= num) ? dp[j - num] + win : -1; // 打，得胜利经验 dp[j] = max(no_use, use); }

本质仍是 01 背包，只是"不选"的价值从 0 变成了lose。

六、常见问题 FAQ

Q1：为什么循环可以从time开始而不是0？

因为当j < time时，物品装不下，dp[j]不会改变，所以可以跳过。两种写法等价

// 写法1（简洁） for (int j = T; j >= time; j--) // 写法2（直观） for (int j = T; j >= 0; j--) { if (j >= time) dp[j] = max(dp[j], dp[j - time] + value); }

Q2：j - time会不会越界？

不会。因为循环条件是j >= time，保证了j - time >= 0。

Q3：dp数组为什么要用long long？

当数据范围较大时，最大价值可能超过int上限（约 21 亿），用long long更安全。

八、结语

背包问题的核心，不在于背模板，而在于理解"正序与倒序"背后的原理：

• 倒序 = 旧值生新值 = 01背包

• 正序 = 新值生新值 = 完全背包

理解了这一点，所有背包变种都能举一反三。

希望这篇文章能帮你彻底搞懂背包问题。如果有任何疑问，欢迎在评论区交流！