算法第四章作业

1. 对贪心算法的理解

  贪心算法从步步最优,以达到全局最优,它所作的每一个选择当前状态下局部最好选择,而可以使用贪心算法的问题,一般来说要满足贪心选择性质和最优子结构性质。

2.汽车加油问题的贪心选择性质

  以样例为例,汽车加满油后可行驶7公里,且旅途中有 7个加油站,k 个加油站与第k-1 个加油站之间的距离分别为1 2 3 4 5 1 6 6,在第一步做贪心选择时,选择在第三个加油站进行加油,则原问题就简化为从第三个加油站开始出发的最少加油次数,此时最优解为3,假设存在另一个解为2,则原问题的解变为3,与原问题最优解为4相矛盾,可证得汽车加油问题满足贪心选择性质。

3. 本章学习过程中遇到的问题及结对编程的情况

  在做题中经常出现部分正确的情况,容易漏掉一些情况。而在结对编程的过程中,一个人所漏掉、想不到的,往往另一个人会发现,这样的话解决问题更加容易。

原文地址:https://www.cnblogs.com/xjsunshine/p/10053366.html