算法第四章作业

1.你对贪心算法的理解

贪心算法在每次做选择的时候并不从整体最优上加以考虑,它所作出的选择只是当前状态下的最好选择。能用贪心算法解决的问题要具有这两个性质:贪心选择性质和最优子结构性质。

贪心选择性质就是问题的整体最优解可以通过一系列的局部最优的选择,即贪心选择来达到。证明这个性质可以用反证法来证明。最优子结构性质:当一个问题的最优解包含其子问

题的最优解时,就具备最优子结构性质。

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

汽车加油问题的贪心选择性质就是如果所剩的油不足够汽车走到下一个加油站时,那么在这站就要加油。

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

本章学习遇到的问题主要是汽车加油问题刚开始我通过的程序非常长而且逻辑有点混乱,伙伴邓汝彬一开始也难以看懂,而且变量设置不大合理,但

后来我们进行探讨,发现我的代码上有很多是可以进行删减的,以贪心算法为核心去进行删减,最后缩减成20行左右的代码通过了,所以结对编程的

效果就完全体现出来了,通过互相的讨论和改进,可以融入两个人不同的想法,促使自己更快的进步。

原文地址:https://www.cnblogs.com/fengwanthousand/p/11908599.html