第7章 贪心算法

目录7.1贪心算法概述7.2典型例题7.1贪心算法贪心算法是一种非常重要且常用的算法思想，它通过在每一步都做出局部最优的选择，来期望最终得到全局最优解。在许多经典问题中，如最短路径、最小生成树等，它是高效且正确的。在本章中，我们将深入探讨贪心算法的基本概念、核心性质（贪心选择性质与最优子结构性质），并通过最优装载、活动选择等典型例题来掌握其实际应用。7.1贪心算法定义：所求问题的整体最优解可以通过一系列局部最优的选择（即贪心选择）来达到。含义：每一步的贪心选择都必须是最终最优解的一部分，即每一步都做出当前看似最好的选择。证明方法：通常使用交换论证法，即证明将贪心选择替换为其他选择，无法得到更优的解。举例：在矩阵中每行选一个数求和最大，贪心选择每行的最大值，该选择一定是全局最优解的一部分。7.1.2贪心选择性质7.1.3最优子结构定义：问题的最优解包含其子问题的最优解。这是贪心算法、动态规划算法等算法的核心特征之一。定义含义：全局最优解可以通过组合局部最优解得到，允许我们自底向上地构建解决方案。含义证明方法：通常使用反证法，即假设全局最优解不包含子问题的最优解，从而推出矛盾，以此证明性质成立。重要性证明方法1.着眼当前，简单高效：每一步都只做局部最优选择，不考虑未来，因此算法简单，效率较高。2.不回溯：一旦做出选择，就不会再回头修改，这与动态规划等算法有本质区别。7.1.4贪心算法的特点问题描述（详细描述见课本）已知每个集装箱的重量及轮船的载重上限，要求将尽可能多的集装箱装上船。贪心策略每次都挑选剩余集装箱中重量最轻的进行装载。选择过程①对所有集装箱按重量从小到大排序。②每次选择最轻的集装箱装船，然后判断是否超重。③重复上一步，直到超重停止。7.2.1最优装载问题描述（详细描述见课本）已知每个活动的开始时间与结束时间，要求安排尽可能多的活动，使得它们在时间上互不冲突。贪心策略每次选择结束时间最早的活动，为后续活动留出更多时间。选择过程按结束时间排序后，依次选择不与已选活动冲突的、结束时间最早的活动。活动选择贪心策略过程示意图7.2.2活动选择核心思路：定义活动结构体存储起止时间，按结束时间升序排序，遍历选择不冲突的活动。核心代码实现（C++）：structblock{intbegin;intend;}a[1000];boolcompare(blocka,blockb){returna.end<b.end;}intmain(){intn,ans=0;cin>>n;for(inti=0;i<n;i++)cin>>a[i].begin>>a[i].end;sort(a,a+n,compare);//按结束时间排序for(inti=0,x=-1;i<n;i++)

{if(a[i].begin>=x){ans++;x=a[i].end;}}cout<<ans<<endl;return0;}活动选择问题程序实现核心概念：贪心算法总结核心思想：每一步都做局部最优选择，期望通过这种方式得到全局最优解。它不回退，仅依据当前信息做决定。适用条件：问题必须具备“贪心选择性质”（局部最优能导出全局最优）和“最优子结构性质”（问题的最优解包含子问题的最优解）。解题步骤：1.分析问题，确定合适的贪心策略（如按某种规则排序）。2.证明策略的正确性，验证其满足贪心选择性质和最优子结构。3.根据策略编写代码实现，通常涉及排序和迭代选择。习题讲解（选择题）1.贪心算法的核心特征是（B）A.通过穷举所有可能解寻找最优解B.每一步选择当前局部最优解C.必须使用动态规划辅助决策D.总是能得到全局最优解2.最优装载问题的主要贪心策略是（B）A.价值最高者优先B.重量最轻者优先C.体积最小者优先D.随机选择习题讲解（判断题