数据结构与算法之贪心算法 C++实现

zj2092

1、基本思路：从问题的某一个初始解触发逐步逼近给定的目标，以尽可能快的求得更好的解。　　当达到算法中某一步不能再继续前进时。就停止算法，给出近似值。也就是说贪心算法并不从总体最优考虑，它所作出的选择仅仅是在某种意义上的局部最优选择。
　　



存在的问题：

1、不能保证最后的解是最优的；

2、不能用来求最大或最小解的问题；

3、仅仅能求满足某些约束条件的可行解的范围。
　　

实现过程：

    从问题的某一初始解出发；

    while （能朝给定总目标前进一步）

    {

          利用可行的决策，求出可行解的一个解元素；

    }

    由全部解元素组合成问题的一个可行解。

贪心算法的基本要素：（对于一个详细的问题，怎么知道是否可用贪心算法解此问题）

（1）、贪心选择性质

  所谓贪心选择性质是指所求问题的总体最优解能够通过一系列局部最优的选择。换句话说。当考虑做何种选择的时候，我们仅仅考虑对当前问题最佳的选择而不考虑子问题的结果。
　　这是贪心算法可行的第一个基本要素。
　　

对于一个详细问题，要确定它是否具有贪心选择性质。必须证明每一步所作的贪心选择终于导致问题的总体最优解。
　　

（2）、最优子结构性质

当一个问题的最优解包括其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。

实例：换零钱

人民币100、50、20、10、5、1、0.5、0.2、01多种纸币。

　　将一定数额的钱数用不能面额组合起来。

代码：
#include<iostream>
const int SIZE = 9;
int coin[SIZE] = {10000, 5000, 2000, 1000, 500, 100, 50, 20, 10};
int num[SIZE];
int exchange(int n);
int main()
{
using namespace std;
double money;
string name[SIZE] = {&quot;一百元&quot;, &quot;五十元&quot;, &quot;二十元&quot;, &quot;十元&quot;, &quot;5元&quot;, &quot;1元&quot;, &quot;5角&quot;, &quot;2角&quot;, &quot;1角&quot;};
cout << &quot;请输入金额:&quot;;
cin >> money;
int n = (int)(money*100);
exchange(n);
for(int i=0; i<SIZE; i++)
{
cout << name << &quot;币种: &quot; << num << &quot; 张\n&quot;;
}
return 0;
}
int exchange(int n)
{
int i;
for (i=0; i<SIZE; i++)
if (n >= coin) break;
while (n>0 && i<SIZE)
{
if(n >= coin)
{
n -= coin;
num++;
}else if(n<10 && n>=5)
{
num[SIZE-1]++;
break;
}else i++;
}
return 0;
}

执行结果：