GESP6级C++考试语法知识（五十三、动态规划----背包问题（六、分组背包）

第六课《宝石分类挑战赛——分组背包》

🎒故事开始：宝石王国大赛

阿宝已经学会了：

✅ 01背包

每件物品最多选一次

✅ 完全背包

每件物品无限选

✅ 多重背包

每件物品有固定数量

1、这一天，宝石王国举行了一场盛大的比赛：

💎 宝石分类挑战赛

2、国王宣布：

勇士们！

你们可以挑选装备参加比赛！

但是每个类别只能选择一种！

3、阿宝来到宝石仓库。

发现宝石被分成了许多组。

（1）武器组

（2）头盔组

（3）鞋子组

4、国王说：

武器只能选一个！

头盔只能选一个！

鞋子只能选一个！

5、阿宝发现：

这和以前的背包完全不同！

第一幕：什么是分组背包？

以前：

1、01背包

（1）每件物品：

选 不选

互不影响。

（2）例如：

宝剑 盾牌 药水

都能同时拿。

2、而现在：

（1）武器组：

木剑 铁剑 圣光剑

（2）只能选：

其中一个

（3）不能：

木剑+铁剑

❌

（4）不能：

铁剑+圣光剑

❌

（5）只能：

木剑

或

铁剑

或

圣光剑

或

一个都不选

3、这就是：

🌟分组背包

第二幕：分组背包定义

1、分组背包：

物品被分成若干组

每组最多选一个

2、例如：

（1）武器组

选一个

（2）头盔组

选一个

（3）鞋子组

选一个

3、🌟口诀

每组最多挑一个， 组内物品不能叠。

第三幕：先看一个小例子

1、背包容量：

4

2、两组物品：

第一组

第二组

问：

最大价值是多少？

第四幕：状态定义

1、仍然定义：

dp[i][j]

表示：

前 i 组物品

容量 j

最大价值

2、注意！

（1）这里的：

i

（2）不再表示：

前i件物品

（3）而是：

前i组物品

3、🌟这是最容易错的地方

（1）01背包：

dp[i][j]

前 i 件物品

（2）分组背包：

dp[i][j]

前 i 组物品

第五幕：状态转移

1、来到第 i 组。

2、这一组有：

若干物品

3、怎么办？

全部试一遍！

4、例如：

（1）武器组：

木剑 铁剑 圣光剑

（2）对于容量 j：

尝试：

选木剑

尝试：

选铁剑

尝试：

选圣光剑

尝试：

一个不选

谁更优选谁。

5、🌟状态转移公式

（1）设：

k

表示组内某个物品。

（2）重量：

w[i][k]

（3）价值：

v[i][k]

（4）那么：

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

（5）含义：

选中了这一组里的某个物品。

第六幕：手算DP表

1、容量：

4

2、第一组：

初始化：

处理第一组。

容量1：

选：

重量1 价值2

得到：

2

容量2：

选：

重量2 价值4

得到：

4

容量3：

仍然选价值更大的：

4

容量4：

4

表格：

第二组：

继续更新。

容量4：

选：

第一组重量2价值4 + 第二组重量1价值3 = 7

或者：

第一组重量1价值2 + 第二组重量3价值5 = 7

答案：

7

最终：

dp[2][4] = 7

第七幕：三层循环结构

1、分组背包最经典结构：

（1）第一层

for(i)

枚举组

（2）第二层

for(j)

枚举容量

（3）第三层

for(k)

枚举组内物品

2、模板：

for(i) { for(j) { for(k) { } } }

3、参考程序：

#include <iostream> #include <algorithm> using namespace std; int dp[105][1005]; int w[105][105]; int v[105][105]; int cnt[105]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>cnt[i]; for(int j=1;j<=cnt[i];j++) { cin>>w[i][j] >>v[i][j]; } } for(int i=1;i<=n;i++) { for(int j=0;j<=m;j++) { dp[i][j]=dp[i-1][j]; for(int k=1;k<=cnt[i];k++) { if(j>=w[i][k]) { dp[i][j] = max( dp[i][j], dp[i-1][j-w[i][k]] + v[i][k] ); } } } } cout<<dp[n][m]; return 0; }

第八幕：压缩成一维进行优化

1、现在开始优化。

（1）压缩成：

dp[j]

（2）如果正序：

for(j=0;j<=m;j++)

（3）可能发生：

同一组选两件

（4）例如：

武器组：

木剑 铁剑

更新木剑后。

又更新铁剑。

结果：

木剑+铁剑

一起选上了！

❌

违反规则！

所以：

还是必须倒序。

2、🌟标准一维转移

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

3、完整一维参考程序

#include <iostream> #include <algorithm> using namespace std; int w[105][105]; int v[105][105]; int cnt[105]; int dp[1005]; int main() { int n,m; cin >> n >> m; for(int i=1;i<=n;i++) { cin >> cnt[i]; for(int j=1;j<=cnt[i];j++) { cin >> w[i][j] >> v[i][j]; } } for(int i=1;i<=n;i++) { for(int j=m;j>=0;j--) { for(int k=1;k<=cnt[i];k++) { if(j >= w[i][k]) { dp[j] = max( dp[j], dp[j-w[i][k]] + v[i][k] ); } } } } cout << dp[m] << endl; return 0; }

🌟更容易理解的写法

很多竞赛书会这样写：

for(int i=1;i<=n;i++) { int old[1005]; for(int j=0;j<=m;j++) old[j]=dp[j]; for(int j=0;j<=m;j++) { for(int k=1;k<=cnt[i];k++) { if(j>=w[i][k]) { dp[j]=max( dp[j], old[j-w[i][k]]+v[i][k] ); } } } }

（1）这里：

old[]

表示：

上一组结束后的状态

（2）于是转移就变成：

当前组 = 从上一组转移

（3）即：

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

这与二维写法：

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

完全一致。

第九幕：生活中的分组背包

1、很多同学会问：

这个模型有什么用？

2、其实非常常见！

选课系统

数学组选一门

英语组选一门

科学组选一门

游戏装备

武器选一件

头盔选一件

鞋子选一件

旅游套餐

机票选一种

酒店选一种

景点套票选一种

全部都是：

🌟分组背包

🎯本课总结

1、分组背包定义

物品分组。

每组：

最多选一个

2、状态定义

dp[i][j]

前 i 组

容量 j

最大价值

3、转移公式

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

枚举组内所有物品。

4、循环结构

for(组) { for(容量) { for(组内物品) { } } }

5、一维优化

容量：

倒序

🏹课后挑战

1、背包容量：

5

2、第一组（武器）

3、第二组（头盔）

4、第三组（鞋子）

5、请同学们：

① 画出完整的dp[i][j]表。

② 求出最终答案。

③ 思考：

6、为什么同一组要使用倒序循环？

恭喜你！已经掌握了分组背包的核心思想！