1.你对贪心算法的理解
贪心算法是通过一系列的选择来得到问题的解。它所做的每一个选择都是当前状态下局部最好选择,既贪心选择。
重要性质:
贪心选择性质:指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各式子问题,而贪心算法则通常以自顶向上的方式进行,以迭代的方式做出相继的贪心选择,每做一次贪心选择就将所求问题简化为规模更小的子问题。
最优子结构性质:当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
2.请说明汽车加油问题的贪心选择性质
每次都判断满油时,是否能到达下一个加油站。在油量支持的情况下,尽量选最远的加油站加油。
3.请说明在本章学习过程中遇到的问题及结对编程的情况
选择合适的贪心策略是一个难点,特别是会场问题时,单纯选择截止时间排序会出现一些情况通过不了。书上的例题和实际的问题解决还是有一点差别的。
跟同学结对讨论确实能更好的开阔自己的思路。
原文:https://www.cnblogs.com/wanghaopeng/p/10055291.html