第八课《背包王国终极试炼——混合背包》故事开始背包王国终极试炼经过前面七节课的修炼阿宝已经掌握了✅ 01背包✅ 完全背包✅ 多重背包✅ 二进制优化✅ 分组背包✅ 方案数背包阿宝觉得自己已经天下无敌了。结果这一天。背包王国召开了最终考试。国王宣布今天的试炼将同时出现各种类型的物品阿宝一听同时出现国王点点头有些物品只能拿一次。有些物品无限拿。有些物品有固定数量。全部混在一起阿宝于是混合背包正式登场第一幕什么是混合背包1、以前的题目很单纯。01背包所有物品只能拿一次完全背包所有物品无限拿多重背包所有物品固定数量2、而现在仓库里有名称重量价值类型圣剑2301魔法药水12完全炸弹35多重(2个)发现了吗每个物品类型不同这就是混合背包第二幕如何识别物品类型1、竞赛题经常这样输入w v s其中w重量v价值s数量2、规定如果s -1表示01背包只能拿一次如果s 0表示完全背包无限拿如果s 0表示多重背包有 s 个3、三种物品同时出现第三幕阿宝的发现阿宝突然想到咦前面不是都学过了吗01背包for(jm;jw;j--)完全背包for(jw;jm;j)多重背包二进制优化 ↓ 变成01背包那是不是每种物品按自己的规则处理就行国王完全正确第四幕混合背包核心思想1、其实混合背包没有新DP2、很多同学第一次学会失望啊就这真的就这3、混合背包本质01背包 完全背包 多重背包放到一起。第五幕一个小例子1、背包容量52、物品重量价值类型230112完全352个问最大价值第六幕处理第一件物品圣剑01背包使用for(jm;jw;j--)更新dp[j] max( dp[j], dp[j-w]v )第七幕处理第二件物品药水完全背包使用for(jw;jm;j)正序更新。因为可以重复使用第八幕处理第三件物品炸弹数量2个先拆。2拆成1 1变成两个01物品重量价值3535然后使用01背包更新。完成第九幕统一模板1、阿宝发现其实只要判断s是什么。2、情况1s-101背包for(jm;jw;j--)3、情况2s0完全背包for(jw;jm;j)4、情况3s0二进制拆分↓01背包第十幕完整程序这是竞赛经典模板。#include iostream #include algorithm using namespace std; int dp[10005]; int main() { int n,m; cinnm; for(int i1;in;i) { int w,v,s; cinwvs; // 01背包 if(s-1) { for(int jm;jw;j--) { dp[j] max( dp[j], dp[j-w]v ); } } // 完全背包 else if(s0) { for(int jw;jm;j) { dp[j] max( dp[j], dp[j-w]v ); } } // 多重背包 else { int k1; while(ks) { int Wk*w; int Vk*v; for(int jm;jW;j--) { dp[j] max( dp[j], dp[j-W]V ); } s-k; k*2; } if(s0) { int Ws*w; int Vs*v; for(int jm;jW;j--) { dp[j] max( dp[j], dp[j-W]V ); } } } } coutdp[m]; return 0; }第十一幕混合背包其实是大集合很多同学学到这里突然发现01背包倒序完全背包正序多重背包二进制优化 倒序全部重新出现了所以混合背包 背包大集合第十二幕考官最爱的问题考官请问为什么01背包倒序因为防止重复选考官为什么完全背包正序因为允许重复选考官多重背包怎么优化二进制拆分考官混合背包怎么做分类讨论你全部回答出来。已经超越很多初学者了本课总结1、混合背包定义同一道题里同时出现01背包 完全背包 多重背包2、核心思想遇到什么类型 就用什么转移3、01背包for(jm;jw;j--)4、完全背包for(jw;jm;j)5、多重背包二进制拆分 ↓ 01背包6、最重要结论01倒着跑 完全正着跑。 多重先拆包 混合分类搞。 背包阶段终极总结到这里我们已经完成了整个背包王国课程课程内容第一课01背包第二课01背包优化第三课完全背包第四课多重背包第五课二进制优化第六课分组背包第七课方案数背包第八课混合背包 下一阶段建议当学生学完这八课后已经掌握了DO的启蒙线性DP二维DP背包DP将来还要学习树形DP还有状态压缩DP还有区间DPDP的道路还有很长我们将来还要继续学习。
GESP6级C++考试语法知识（五十五、动态规划----背包问题（八、混合背包）
第八课《背包王国终极试炼——混合背包》故事开始背包王国终极试炼经过前面七节课的修炼阿宝已经掌握了✅ 01背包✅ 完全背包✅ 多重背包✅ 二进制优化✅ 分组背包✅ 方案数背包阿宝觉得自己已经天下无敌了。结果这一天。背包王国召开了最终考试。国王宣布今天的试炼将同时出现各种类型的物品阿宝一听同时出现国王点点头有些物品只能拿一次。有些物品无限拿。有些物品有固定数量。全部混在一起阿宝于是混合背包正式登场第一幕什么是混合背包1、以前的题目很单纯。01背包所有物品只能拿一次完全背包所有物品无限拿多重背包所有物品固定数量2、而现在仓库里有名称重量价值类型圣剑2301魔法药水12完全炸弹35多重(2个)发现了吗每个物品类型不同这就是混合背包第二幕如何识别物品类型1、竞赛题经常这样输入w v s其中w重量v价值s数量2、规定如果s -1表示01背包只能拿一次如果s 0表示完全背包无限拿如果s 0表示多重背包有 s 个3、三种物品同时出现第三幕阿宝的发现阿宝突然想到咦前面不是都学过了吗01背包for(jm;jw;j--)完全背包for(jw;jm;j)多重背包二进制优化 ↓ 变成01背包那是不是每种物品按自己的规则处理就行国王完全正确第四幕混合背包核心思想1、其实混合背包没有新DP2、很多同学第一次学会失望啊就这真的就这3、混合背包本质01背包 完全背包 多重背包放到一起。第五幕一个小例子1、背包容量52、物品重量价值类型230112完全352个问最大价值第六幕处理第一件物品圣剑01背包使用for(jm;jw;j--)更新dp[j] max( dp[j], dp[j-w]v )第七幕处理第二件物品药水完全背包使用for(jw;jm;j)正序更新。因为可以重复使用第八幕处理第三件物品炸弹数量2个先拆。2拆成1 1变成两个01物品重量价值3535然后使用01背包更新。完成第九幕统一模板1、阿宝发现其实只要判断s是什么。2、情况1s-101背包for(jm;jw;j--)3、情况2s0完全背包for(jw;jm;j)4、情况3s0二进制拆分↓01背包第十幕完整程序这是竞赛经典模板。#include iostream #include algorithm using namespace std; int dp[10005]; int main() { int n,m; cinnm; for(int i1;in;i) { int w,v,s; cinwvs; // 01背包 if(s-1) { for(int jm;jw;j--) { dp[j] max( dp[j], dp[j-w]v ); } } // 完全背包 else if(s0) { for(int jw;jm;j) { dp[j] max( dp[j], dp[j-w]v ); } } // 多重背包 else { int k1; while(ks) { int Wk*w; int Vk*v; for(int jm;jW;j--) { dp[j] max( dp[j], dp[j-W]V ); } s-k; k*2; } if(s0) { int Ws*w; int Vs*v; for(int jm;jW;j--) { dp[j] max( dp[j], dp[j-W]V ); } } } } coutdp[m]; return 0; }第十一幕混合背包其实是大集合很多同学学到这里突然发现01背包倒序完全背包正序多重背包二进制优化 倒序全部重新出现了所以混合背包 背包大集合第十二幕考官最爱的问题考官请问为什么01背包倒序因为防止重复选考官为什么完全背包正序因为允许重复选考官多重背包怎么优化二进制拆分考官混合背包怎么做分类讨论你全部回答出来。已经超越很多初学者了本课总结1、混合背包定义同一道题里同时出现01背包 完全背包 多重背包2、核心思想遇到什么类型 就用什么转移3、01背包for(jm;jw;j--)4、完全背包for(jw;jm;j)5、多重背包二进制拆分 ↓ 01背包6、最重要结论01倒着跑 完全正着跑。 多重先拆包 混合分类搞。 背包阶段终极总结到这里我们已经完成了整个背包王国课程课程内容第一课01背包第二课01背包优化第三课完全背包第四课多重背包第五课二进制优化第六课分组背包第七课方案数背包第八课混合背包 下一阶段建议当学生学完这八课后已经掌握了DO的启蒙线性DP二维DP背包DP将来还要学习树形DP还有状态压缩DP还有区间DPDP的道路还有很长我们将来还要继续学习。
