第五课《分身术卷轴——二进制优化》故事开始阿宝的新烦恼1、上一课阿宝学会了多重背包2、每种物品有固定数量。例如物品重量价值数量宝剑233把可以拿0把 1把 2把 3把3、状态转移dp[i][j] max( dp[i-1][j-k*w[i]] k*v[i] )其中k表示拿几件。阿宝觉得很不错。4、结果第二天国王拿来了一张清单武器重量价值数量药水231000瓶........5、阿宝当场傻眼for(k0;k1000;k)如果有很多种物品100种每种1000件程序会慢得像乌龟一样到底怎么办呢第一幕神秘二进制登场1、阿宝找到汉克老师。汉克老师拿出一本算法书《二进制组合术》2、汉克老师说阿宝其实1000件物品不需要一件一件处理3、阿宝什么难道还能合并4、汉克老师不仅能合并还能变成01背包第二幕先理解二进制的力量1、假设有13把宝剑2、阿宝想0把 1把 2把 3把 ... 13把都要枚举。3、汉克老师说我们换一种方法我们把13拆开。拆成1 2 4 64、阿宝为什么是这样5、因为1 2 4 6 136、更神奇的是利用这4组我们能拼出0~13所有数量7、例如17把124210把46313把1246全部都能表示第三幕为什么要拆成1、2、41、因为1 2 4 8 16 32 ...是二进制2、例如113二进制11012表示8 4 13所以任何数字都能由1 2 4 8 16 ...组合出来。第四幕真正的拆分方法1、假设数量 131第一组1剩122第二组2剩103第三组4剩64第四组剩余不足8。直接全部拿走65得到1 2 4 62、万能拆分代码int cnt s; for(int k1;kcnt;k*2) { cnt - k; }最后剩余部分单独处理。3、另一种写法int k 1; while(k s) { s - k; k * 2; }竞赛中一般写成下面这种模板。第五幕把一件物品变成很多件01物品1、原来重量价值数量23132、拆分后1第一组1件重量2×12价值3×132第二组2件重量2×24价值3×263第三组4件重量2×48价值3×4124第四组6件重量2×612价值3×6185得到重量价值234681212183、神奇的事情发生了这些物品每个只能选一次4、因此多重背包变成了01背包第六幕为什么正确1、很多同学第一次学到这里都会怀疑这样不会丢失方案吗2、我们来验证。拆分1 2 4 65、想拿5件怎么办选146、想拿9件选1267、想拿13件选12468、所有数量0~13全部都能表示不会漏第七幕时间复杂度发生了什么1、原来1000件需要枚举1000次2、拆分后1 2 4 8 16 32 64 128 256 4893、只有10组左右。4、为什么因为2¹⁰≈10245、于是时间复杂度从O(nms)变成O(nm log s)速度快速提升第八幕标准拆分代码1、假设w2、重量v3、价值s4、数量int k 1; while(k s) { W[cnt] k * w; V[cnt] k * v; s - k; k * 2; } if(s 0) { W[cnt] s * w; V[cnt] s * v; }5、例如s13得到1 2 4 6对应的新物品。第九幕接下来就是01背包1、拆完以后。直接使用01背包方法for(int i1;icnt;i) { for(int jm;jW[i];j--) { dp[j] max( dp[j], dp[j-W[i]]V[i] ); } }2、因为已经变成每件只能选一次3、所以倒序循环第十幕完整参考程序#include iostream #include algorithm using namespace std; int main() { int n,m; cinnm; int W[10005]; int V[10005]; int cnt 0; for(int i1;in;i) { int w,v,s; cinwvs; int k 1; while(k s) { W[cnt] k*w; V[cnt] k*v; s - k; k * 2; } if(s 0) { W[cnt] s*w; V[cnt] s*v; } } int dp[10005]{0}; for(int i1;icnt;i) { for(int jm;jW[i];j--) { dp[j] max( dp[j], dp[j-W[i]] V[i] ); } } coutdp[m]; return 0; }第十一幕三种背包统一了经过学习。阿宝发现1、01背包数量1直接做。2、完全背包数量∞正序。3、多重背包数量有限个先拆分。再变成01背包。4、于是背包三兄弟类型数量01背包1完全背包无限多重背包有限本课总结1、核心思想把有限个物品拆成1 2 4 8 ...若干组。2、拆分结果例如13拆成1 2 4 63、优化效果原来O(nms)现在O(nm log s)4、重要结论多重背包不好做 二进制来帮忙。 拆成若干01包 速度立刻变飞翔课后挑战1、有一种魔法药水重量价值数量35112、请同学们① 用二进制优化拆分。② 写出所有新物品的重量和价值。③ 验证0~11瓶是否都能表示出来。3、如果你能够自己完成这道题那么你已经掌握了信息学竞赛中经典的优化技巧之一——二进制优化多重背包。
GESP6级C++考试语法知识（五十二、动态规划----背包问题（五、二进制优化多重背包）
第五课《分身术卷轴——二进制优化》故事开始阿宝的新烦恼1、上一课阿宝学会了多重背包2、每种物品有固定数量。例如物品重量价值数量宝剑233把可以拿0把 1把 2把 3把3、状态转移dp[i][j] max( dp[i-1][j-k*w[i]] k*v[i] )其中k表示拿几件。阿宝觉得很不错。4、结果第二天国王拿来了一张清单武器重量价值数量药水231000瓶........5、阿宝当场傻眼for(k0;k1000;k)如果有很多种物品100种每种1000件程序会慢得像乌龟一样到底怎么办呢第一幕神秘二进制登场1、阿宝找到汉克老师。汉克老师拿出一本算法书《二进制组合术》2、汉克老师说阿宝其实1000件物品不需要一件一件处理3、阿宝什么难道还能合并4、汉克老师不仅能合并还能变成01背包第二幕先理解二进制的力量1、假设有13把宝剑2、阿宝想0把 1把 2把 3把 ... 13把都要枚举。3、汉克老师说我们换一种方法我们把13拆开。拆成1 2 4 64、阿宝为什么是这样5、因为1 2 4 6 136、更神奇的是利用这4组我们能拼出0~13所有数量7、例如17把124210把46313把1246全部都能表示第三幕为什么要拆成1、2、41、因为1 2 4 8 16 32 ...是二进制2、例如113二进制11012表示8 4 13所以任何数字都能由1 2 4 8 16 ...组合出来。第四幕真正的拆分方法1、假设数量 131第一组1剩122第二组2剩103第三组4剩64第四组剩余不足8。直接全部拿走65得到1 2 4 62、万能拆分代码int cnt s; for(int k1;kcnt;k*2) { cnt - k; }最后剩余部分单独处理。3、另一种写法int k 1; while(k s) { s - k; k * 2; }竞赛中一般写成下面这种模板。第五幕把一件物品变成很多件01物品1、原来重量价值数量23132、拆分后1第一组1件重量2×12价值3×132第二组2件重量2×24价值3×263第三组4件重量2×48价值3×4124第四组6件重量2×612价值3×6185得到重量价值234681212183、神奇的事情发生了这些物品每个只能选一次4、因此多重背包变成了01背包第六幕为什么正确1、很多同学第一次学到这里都会怀疑这样不会丢失方案吗2、我们来验证。拆分1 2 4 65、想拿5件怎么办选146、想拿9件选1267、想拿13件选12468、所有数量0~13全部都能表示不会漏第七幕时间复杂度发生了什么1、原来1000件需要枚举1000次2、拆分后1 2 4 8 16 32 64 128 256 4893、只有10组左右。4、为什么因为2¹⁰≈10245、于是时间复杂度从O(nms)变成O(nm log s)速度快速提升第八幕标准拆分代码1、假设w2、重量v3、价值s4、数量int k 1; while(k s) { W[cnt] k * w; V[cnt] k * v; s - k; k * 2; } if(s 0) { W[cnt] s * w; V[cnt] s * v; }5、例如s13得到1 2 4 6对应的新物品。第九幕接下来就是01背包1、拆完以后。直接使用01背包方法for(int i1;icnt;i) { for(int jm;jW[i];j--) { dp[j] max( dp[j], dp[j-W[i]]V[i] ); } }2、因为已经变成每件只能选一次3、所以倒序循环第十幕完整参考程序#include iostream #include algorithm using namespace std; int main() { int n,m; cinnm; int W[10005]; int V[10005]; int cnt 0; for(int i1;in;i) { int w,v,s; cinwvs; int k 1; while(k s) { W[cnt] k*w; V[cnt] k*v; s - k; k * 2; } if(s 0) { W[cnt] s*w; V[cnt] s*v; } } int dp[10005]{0}; for(int i1;icnt;i) { for(int jm;jW[i];j--) { dp[j] max( dp[j], dp[j-W[i]] V[i] ); } } coutdp[m]; return 0; }第十一幕三种背包统一了经过学习。阿宝发现1、01背包数量1直接做。2、完全背包数量∞正序。3、多重背包数量有限个先拆分。再变成01背包。4、于是背包三兄弟类型数量01背包1完全背包无限多重背包有限本课总结1、核心思想把有限个物品拆成1 2 4 8 ...若干组。2、拆分结果例如13拆成1 2 4 63、优化效果原来O(nms)现在O(nm log s)4、重要结论多重背包不好做 二进制来帮忙。 拆成若干01包 速度立刻变飞翔课后挑战1、有一种魔法药水重量价值数量35112、请同学们① 用二进制优化拆分。② 写出所有新物品的重量和价值。③ 验证0~11瓶是否都能表示出来。3、如果你能够自己完成这道题那么你已经掌握了信息学竞赛中经典的优化技巧之一——二进制优化多重背包。
