贪心算法贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么？怎样说明一个问题具有贪心选择呢

什么是贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

C语言算法，用贪心法

贪心算法虽然不是最好的，但毕竟是你要求的。

。

。

随机取一个人， 循环开始：随机取一个没接水的人， 比较两个人的接水时间大小，让小的先接。

累加总等待时间为接水时间。

循环体结束。

输出平均接水等待时间累加T/人数n

贪心算法中，通常会让证明贪心选择性，请问，证明贪心选择性的实质是什么？怎样说明一个问题具有贪心选择呢

贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择来得到。

就是说，你需要证明当前问题可以通过选择最好的那个元素（比如01背包，总能够通过选择当前重量最小的物品来得到最优解）来解决问题 证明：（每一步所做的贪心选择最终导致问题的整体最优解） //基本思路：考察一个问题的最优解，证明可修改该最优解，使得其从贪心选择开始，然后用数学归纳法证明每一步都可以通过贪心选择得到最优解 1，假定首选元素不是贪心选择所要的元素，证明将首元素替换成贪心选择所需元素，依然得到最优解； 2，数学归纳法证明每一步均可通过贪心选择得到最优解