德持建设集团有限公司网站网站地图 seo

德持建设集团有限公司网站,网站地图 seo,品牌策划与推广方案,网站分析步骤一、二进制优化的核心思想1. 基本原理把一个正整数 s 拆分成若干个2的幂次方#xff08;1, 2, 4, 8, ...#xff09;的和#xff0c;再加上剩余的零头。例如#xff1a;s 13拆分成#xff1a;1 2 4 6这样就可以用4个组表示0-13的所有数字2. 数学原理任何一个正整数n都…一、二进制优化的核心思想1. 基本原理把一个正整数s拆分成若干个2的幂次方1, 2, 4, 8, ...的和再加上剩余的零头。例如s 13拆分成1 2 4 6这样就可以用4个组表示0-13的所有数字2. 数学原理任何一个正整数n都可以表示为n a₀·2⁰ a₁·2¹ a₂·2² ... aₖ·2ᵏ r其中aᵢ是0或1r是剩余部分小于2ᵏ⁺¹二、二进制优化的方法步骤1物品拆分对于每种物品体积v价值w数量svectorpairint, int items; // 存储拆分后的物品体积价值 int k 1; // 从1开始 ​ while (s 0) { int amount min(k, s); // 这一组的数量 items.push_back({v * amount, w * amount}); // 打包成一组 s - amount; k * 2; // 幂次增加 }步骤2转换为01背包拆分后对每组物品使用01背包算法for (auto item : items) { int v_group item.first; // 这一组的总体积 int w_group item.second; // 这一组的总价值 for (int j V; j v_group; j--) { dp[j] max(dp[j], dp[j - v_group] w_group); } }三、使用要点1.什么时候使用二进制优化情况1物品数量s很大比如s ≥ 20情况2背包容量V较大V ≥ 1000情况3物品种类n较多n ≥ 502.二进制优化的优点原始方法二进制优化后每个物品拆成s个每个物品拆成log₂(s)个时间复杂度O(n × s × V)时间复杂度O(n × log(s) × V)物品总数 ∑s物品总数 ∑log₂(s)3.拆分的边界情况// 正确写法 while (k s) { items.push_back({v * k, w * k}); s - k; k * 2; } if (s 0) { items.push_back({v * s, w * s}); }四、适用场景分析场景1多重背包问题// 问题描述n种物品每种物品有体积v[i]价值w[i]数量s[i] // 背包容量V求最大价值✅必须用二进制优化的情况n 100, s[i] 1000, V 1000计算量100×1000×1000 1亿 → 100×10×1000 100万优化100倍场景2完全背包问题// 完全背包每种物品可以取无限次❌不能用二进制优化需要用完全背包的递推公式for (int j v[i]; j V; j) { dp[j] max(dp[j], dp[j - v[i]] w[i]); }场景3混合背包问题// 有些物品只能取1次01背包 // 有些物品可以取无限次完全背包 // 有些物品可以取有限次多重背包✅部分用二进制优化if (s -1) // 01背包 // 直接处理 else if (s 0) // 完全背包 // 完全背包处理 else // 多重背包 // 二进制优化后处理五、代码模板#include iostream #include vector using namespace std; ​ int main() { int n, V; cin n V; vectorint dp(V 1, 0); vectorpairint, int items; // 存放(体积, 价值) // 读取并拆分物品 for (int i 0; i n; i) { int v, w, s; cin v w s; // 二进制拆分 int k 1; while (k s) { items.push_back({v * k, w * k}); s - k; k * 2; } if (s 0) { items.push_back({v * s, w * s}); } } // 01背包 for (auto item : items) { for (int j V; j item.first; j--) { dp[j] max(dp[j], dp[j - item.first] item.second); } } cout dp[V] endl; return 0; }六、复杂度分析优化前后对比假设n100, 平均s1000, V1000方法物品总数循环次数时间估算朴素拆分100×1000100,000100,000×10001亿约1秒二进制优化100×101,0001,000×1000100万约0.01秒七、注意事项1.不要过度拆分如果s很小比如s ≤ 10直接朴素拆分即可二进制优化反而增加复杂度。2.注意数据范围// 错误可能会溢出 items.push_back({v * k, w * k}); // 正确确保在int范围内 int group_v v * k; int group_w w * k; if (group_v V) break; // 如果单组体积超过背包容量可以跳过 items.push_back({group_v, group_w});3.优化技巧// 提前剪枝如果物品总体积 背包容量直接按完全背包处理 if (v * s V) { // 转换为完全背包 for (int j v; j V; j) { dp[j] max(dp[j], dp[j - v] w); } continue; }八、总结口诀物品数量多拆分要巧妙 二进制优化效率提高高。 二幂来打包零头单独搞 转成01包问题解决了。记住当s 20时考虑二进制优化当s很小或V很小时直接朴素拆分即可。