算法第四章作业

1. 你对贪心算法的理解（2分）
   贪心算法的实质就是对于所要求解的问题的整体最优解可以通过一系列的局部最优的选择来得到。在使用贪心算法时，我们要做的就是在当前状态下做出最好的选择即可，并不依赖将来要做的选择，也不依赖子问题的解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
2. 请说明汽车加油问题的贪心选择性质（2分）
   对于汽车加油的问题，我们要考虑的是汽车加满油最多能走多远，直到汽车没办法开到下一个加油站的时候才加油，这就是贪心算法思想的体现。体现在算法上则是
   

   def ToGetDestination(n, k, distances):
       count = 0 //记录停下来加油了几次
       i = 0
       val = n //满油状态下，汽车能行驶的距离
       while(i <= k):
           if(n >= distances[i]): //汽车当前的剩余行驶量能够到达下一个地点时，就继续往下开
               n = n - distances[i]
               i = i + 1
           else: //汽车剩余行驶量无法到达下一个地点时，要在这里加满油，即n = val
               n = val
               count = count + 1
       return count

3. 请说明在本章学习过程中遇到的问题及结对编程的情况（1分）
   在本章的学习过程中，掌握了贪心算法的基本使用，感觉要比动态规划算法要容易理解，在使用上也更加便捷。一开始在写会场安排那道题目的时候，没有考虑到相同开始时间相同但是结尾时间不同的情况，导致一开始只能通过两个答案，在和队友再次审视那道题目的时候最后还是发现了这个问题，最后还是解决了。

算法第四章作业

原文：https://www.cnblogs.com/bhwfsj/p/10043211.html