【算法】贪心算法

1. 贪心介绍

贪心算法总是做出当前最好的选择，期望通过局部最优选择得到全局最优的解决方案。但贪心不是从整体最优来考虑的，一旦做出选择，不会再改变，只能达到某种意义上的局部最优。

简记为：想要当下最好的，但会导致目光短浅

2. 贪心本质

应用情景：当出现两个特性——贪心选择性质和最优子结构性质时可用。

（1）贪心选择性质：指原问题的整体最优解可以通过一系列局部最优的选择得到。运用同一规则，原问题可拆分为一个个相似的子问题，而后的每一步都是当前最优的选择。但其依赖于当前已做出的选择，无回溯过程。

（2）最优子结构性质：指一个问题的最优解包含其子问题的最优解。如：原问题：S={a1,a2,a3,ai...an}，转化为子问题：{ai},S-{ai}。即通过贪心选择当前最优解{ai}后，转化为求解子问题S-{ai}。

求解步骤：
（1）贪心策略：选择当前看上去最好的一个。如：最红的苹果是最好的，则每一次都选择最红的。
（2）局部最优解：每一次取到的结果记为ak（k=1，2，3…）
（3）全局最优解：把所有局部最优解整合为一个最优解{a1,a2,…}

3. 最优装载问题

有一天，海盗们截获了一艘装满各种各样古董的货船，每件古董都价值连城，一旦打碎就失去了价值。虽然海盗船足够大，但载重为c，每件古董的重量为wi，海盗们绞尽脑汁要把尽可能多的宝贝装上海盗船，该怎么办呢？

假设c为30，8件古董，价值分别为4，10，7，11，3，5，14，2

（1）问题分析

尽可能多：排序，每次选最小的装入

（2）算法实现

可以用一维数组w[]存储古董的数量

（1）借助c++中的排序函数sort
（头文件#include<algorithm>）

排序算法如下：

sort(begin,end)//参数begin和end表示一个范围，分别为待排序数组的首地址和尾地址，默认为升序

（2）代码如下：

double tmp=0.0;//tmp为已装载到船上的古董的重量
int ans=0;//ans为已装载的古董个数
for(int i=0;i<n;i++)
{twp+=w[i];if(tmp<=c)ans++;elsebreak;
}
cout<<ans<<endl;

（3）算法分析

（1）时间复杂度：
①sort函数，平均时间复杂度为O(nlogn)；
②输入和贪心策略求解的两个for循环均为O(n)；
故，总的为O(nlogn)。

（2）空间复杂度：在程序中使用了tmp、ans等辅助变量，为O(1)。