第六课《宝石分类挑战赛——分组背包》故事开始宝石王国大赛阿宝已经学会了✅ 01背包每件物品最多选一次✅ 完全背包每件物品无限选✅ 多重背包每件物品有固定数量1、这一天宝石王国举行了一场盛大的比赛 宝石分类挑战赛2、国王宣布勇士们你们可以挑选装备参加比赛但是每个类别只能选择一种3、阿宝来到宝石仓库。发现宝石被分成了许多组。1武器组名称重量价值木剑12铁剑24圣光剑372头盔组名称重量价值布帽11铁盔233鞋子组名称重量价值草鞋12魔法靴254、国王说武器只能选一个头盔只能选一个鞋子只能选一个5、阿宝发现这和以前的背包完全不同第一幕什么是分组背包以前1、01背包1每件物品选 不选互不影响。2例如宝剑 盾牌 药水都能同时拿。2、而现在1武器组木剑 铁剑 圣光剑2只能选其中一个3不能木剑铁剑❌4不能铁剑圣光剑❌5只能木剑或铁剑或圣光剑或一个都不选3、这就是分组背包第二幕分组背包定义1、分组背包物品被分成若干组每组最多选一个2、例如1武器组选一个2头盔组选一个3鞋子组选一个3、口诀每组最多挑一个 组内物品不能叠。第三幕先看一个小例子1、背包容量42、两组物品第一组重量价值1224第二组重量价值1335问最大价值是多少第四幕状态定义1、仍然定义dp[i][j]表示前 i 组物品容量 j最大价值2、注意1这里的i2不再表示前i件物品3而是前i组物品3、这是最容易错的地方101背包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、容量42、第一组重量价值1224初始化i\j01234000000处理第一组。容量1选重量1 价值2得到2容量2选重量2 价值4得到4容量3仍然选价值更大的4容量44表格i\j01234000000102444第二组重量价值1335继续更新。容量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; cinnm; for(int i1;in;i) { cincnt[i]; for(int j1;jcnt[i];j) { cinw[i][j] v[i][j]; } } for(int i1;in;i) { for(int j0;jm;j) { dp[i][j]dp[i-1][j]; for(int k1;kcnt[i];k) { if(jw[i][k]) { dp[i][j] max( dp[i][j], dp[i-1][j-w[i][k]] v[i][k] ); } } } } coutdp[n][m]; return 0; }第八幕压缩成一维进行优化1、现在开始优化。1压缩成dp[j]2如果正序for(j0;jm;j)3可能发生同一组选两件4例如武器组木剑 铁剑更新木剑后。又更新铁剑。结果木剑铁剑一起选上了❌违反规则所以还是必须倒序。2、标准一维转移for(int i1;in;i) { for(int jm;j0;j--) { for(int k1;kcnt[i];k) { if(jw[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 i1;in;i) { cin cnt[i]; for(int j1;jcnt[i];j) { cin w[i][j] v[i][j]; } } for(int i1;in;i) { for(int jm;j0;j--) { for(int k1;kcnt[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 i1;in;i) { int old[1005]; for(int j0;jm;j) old[j]dp[j]; for(int j0;jm;j) { for(int k1;kcnt[i];k) { if(jw[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、背包容量52、第一组武器重量价值12353、第二组头盔重量价值23344、第三组鞋子重量价值12245、请同学们① 画出完整的dp[i][j]表。② 求出最终答案。③ 思考6、为什么同一组要使用倒序循环恭喜你已经掌握了分组背包的核心思想