GESP6级C++考试语法知识（四十八、动态规划----背包问题（一、01背包基础）

第一课《神奇背包的诞生——01背包》

1、🎒 欢迎来到背包王国！

同学们，今天我们要学习动态规划家族中最著名、最经典的一位成员：

🌟 01背包

2、很多同学第一次接触背包问题时都会觉得：

“这不就是装东西吗？”

没错！

但是当东西变多以后，问题就变得非常厉害了！

3、今天，我们跟着小勇士阿宝，一起进入：

🏰《宝藏森林大冒险》

第一幕：宝藏森林出现了！

1、一天，阿宝收到了一封信：

尊敬的小勇士：

宝藏森林出现了许多珍贵宝物！

如果你能合理装满背包，就能获得最多财富！

阿宝高兴极了，立刻背上背包出发。

可是到了森林门口，守卫拦住了他：

2、👮守卫说：

你的背包最多只能承重4公斤！

阿宝点点头。

3、森林里有三件宝物：

4、🤔 问题来了

容量：

4公斤

如何装，才能获得最大价值？

第二幕：暴力枚举法

1、阿宝开始一个一个尝试。

情况1

什么都不拿

价值：

0

情况2

只拿金币石

重量：

1

价值：

15

情况3

只拿钻石

重量：

3

价值：

20

情况4

只拿魔法水晶

重量：

4

价值：

30

情况5

金币石 + 钻石

重量：

1+3=4

价值：

15+20=35

✅ 可以装

情况6

金币石 + 魔法水晶

重量：

5

❌ 超重

情况7

钻石 + 魔法水晶

重量：

7

❌ 超重

情况8

全拿

重量：

8

❌ 超重

最终答案：

金币石 + 钻石 价值35

第三幕：宝物越来越多怎么办？

1、阿宝第二天又来了。

这次森林里有：

30件宝物

第三天：

100件宝物

第四天：

1000件宝物

2、阿宝崩溃了。

因为：

每件宝物都有两种选择：

拿 不拿

3件宝物：

2³ = 8种情况

10件宝物：

2¹⁰ = 1024种

20件宝物：

2²⁰ ≈ 100万种

100件宝物：

天文数字

根本算不过来！

怎么办？

第四幕：DP魔法登场！

1、汉克老师出现了，他说：

同学，不要重复思考！

把已经算过的结果记下来！

2、使用：

🌟 动态规划（DP）

Dynamic Programming

解决背包问题。

第五幕：建立状态

1、我们先思考：

前几个宝物

剩多少容量

就能决定答案

2、于是定义：

dp[i][j]

表示：

前 i 件物品

背包容量为 j

能获得的最大价值

3、举例

dp[2][4]

表示：

前2件宝物

容量4

最大价值是多少

第六幕：最重要的思考

1、假设现在考虑第 i 件物品。

会发生什么？

其实只有两种情况：

2、第一种

不拿它

（1）例如：

第3件宝物不拿

（2）那么答案来自：

dp[i-1][j]

（3）意思：

前面已经算好了

直接继承

3、第二种

拿它

（1）假设：

重量：

w[i]

价值：

v[i]

（2）拿了以后：

容量减少：

j-w[i]

价值增加：

v[i]

（3）因此：

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

第七幕：状态转移方程

1、两种方案谁更好？

取最大值！

2、于是得到：

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

3、这是01背包最核心的公式！

记住：

（1）不拿

dp[i-1][j]

（2）拿

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

（3）取最大

max(...)

第八幕：手算一个例子

1、🌟建立DP表

宝物：

背包容量：

4

2、dp定义

dp[i][j]

表示：

前 i 件宝物

背包容量为 j

能获得的最大价值

3、第0行（什么宝物都没有）

（1）先初始化：

dp[0][j]

（2）因为没有宝物。

无论背包容量多少：

价值都是0。

4、第一件宝物

（1）宝物1：

重量=1 价值=15

（2）容量0

装不进去：

dp[1][0]=0

（3）容量1

不拿：

dp[0][1]=0

拿：

dp[0][0]+15 = 15

取最大：

dp[1][1]=15

（4）容量2

不拿：

dp[0][2]=0

拿：

dp[0][1]+15 = 15

所以：

dp[1][2]=15

（5）同理：

dp[1][3]=15 dp[1][4]=15

（6）表格变成：

5、第二件宝物

（1）宝物2：

重量=3 价值=20

（2）容量0

dp[2][0]=0

（3）容量1

装不下。

只能继承：

dp[2][1] = dp[1][1] = 15

（4）容量2

装不下。

dp[2][2] = dp[1][2] = 15

（5）容量3

开始精彩了！

不拿

dp[1][3] = 15

拿

拿了宝物2以后：

剩余容量：

3-3=0

价值：

dp[1][0]+20 = 20

比较：

max(15,20) = 20

所以：

dp[2][3]=20

（6）容量4

不拿

dp[1][4] = 15

拿

拿宝物2后：

剩余容量：

4-3=1

还能利用：

dp[1][1] = 15

总价值：

15+20 = 35

比较：

max(15,35) = 35

所以：

dp[2][4]=35

（7）表格变成：

6、第三件宝物

（1）宝物3：

重量=4 价值=30

（2）容量0

dp[3][0]=0

（3）容量1

装不下：

dp[3][1] = dp[2][1] = 15

（4）容量2

装不下：

dp[3][2] = dp[2][2] = 15

（5）容量3

装不下：

dp[3][3] = dp[2][3] = 20

（6）容量4

终于能装下。

不拿

dp[2][4] = 35

拿

拿宝物3：

剩余容量：

4-4=0

价值：

dp[2][0]+30 = 30

比较：

max(35,30) = 35

因此：

dp[3][4] = 35

（7）最终表格：

7、🌟最后答案

（1）看哪里？

永远看：

dp[n][m]

这里：

n=3 m=4

所以：

dp[3][4] = 35

答案：

35

（2）对应方案：

宝物1（金币石） + 宝物2（钻石）

总重量：

1+3=4

总价值：

15+20=35

8、🎯给学生们的一个重要观察

1、很多同学，学 DP 时最容易忽略的一件事：

不要只看数字！

一定要看：

dp[i][j]

中的

i 是谁？

j 是谁？

2、例如：

dp[2][4]

它表示：

只看前2件宝物，

背包容量4，

最大价值是多少？

3、当同学们：

能够把每一个格子的实际意义说出来时，说明你已经真正理解了 DP，而不是在背公式。这个习惯对于以后学习完全背包、多重背包、区间DP、树形DP都非常重要。

第九幕：参考代码：

#include <iostream> #include <algorithm> using namespace std; int main() { int n = 3; int m = 4; int w[4] = {0,1,3,4}; int v[4] = {0,15,20,30}; int dp[10][10] = {}; for(int i = 1; i <= n; i++) { for(int j = 0; j <= m; 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][m]; return 0; }

输出：

35

第十幕：为什么叫01背包？

1、很多同学会问：

为什么叫：

01背包

呢？

2、因为每件物品只有两种状态：

0 = 不选 1 = 选

3、例如：

表示：

选金币石 选钻石 不选水晶

4、所以叫：

🎒01背包

第十一幕：0/1背包判断口诀

1、以后看到题目：

每件物品只能选一次

并且

求最大价值

那么立刻想到：

01背包

2、例如：

（1）题目1

考试时间有限。

每道题：

耗时 分数

每题只能做一次。

求最高得分。

👉 01背包

（2）题目2

旅游购物。

每件商品：

价格 快乐值

只能买一次。

预算有限。

求最大快乐值。

👉 01背包

（3）题目3

选择课程。

每门课：

学时 收益

只能选一次。

时间有限。

求最大收益。

👉 01背包

🎯 本课总结

1、今天学会了：

什么是01背包

每件物品：

选 不选

2、状态定义

dp[i][j]

前i件物品

容量j

最大价值

3、状态转移

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

4、判断方法

看到：

✅ 每件物品只能选一次

✅ 有容量限制

✅ 求最优值

立刻想到：

🌟01背包DP

🏹 课后挑战

有一个容量为 5 的背包。

请同学们自己尝试：

1. 用枚举法求答案。

2. 画出 DP 表格。

3. 求出最大价值。

4. 最后写一下DP程序代码