博客

贪心

算法

(1)原理：


在对问题求解时，总是做出在


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

。

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

(2)特性：

贪心算法采用


自顶向下


，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。能够用贪心算法求解的问题一般具有两个重要特性：


贪心选择性质


和


最优子结构性质


。

活动安排问题代码如下：

#include “stdafx.h”

#include <iostream>

using namespace std;

template<class Type>

void GreedySelector(int n, Type s[], Type f[], bool A[]);

const int N = 11;

int main()

{

//下标从1开始,存储活动开始时间

int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};

//下标从1开始,存储活动结束时间

int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};

bool A[N+1];

cout<<“各活动的开始时间,结束时间分别为：”<<endl;

for(int i=1;i<=N;i++)

{

cout<<“[“<<i<<“]:”<<“(“<<s[i]<<“,”<<f[i]<<“)”<<endl;

}

GreedySelector(N,s,f,A);

cout<<“最大相容活动子集为：”<<endl;

for(int i=1;i<=N;i++)

{

if(A[i]){

cout<<“[“<<i<<“]:”<<“(“<<s[i]<<“,”<<f[i]<<“)”<<endl;

}

}

return 0;

}

template<class Type>

void GreedySelector(int n, Type s[], Type f[], bool A[])

{

A[1]=true;

int j=1;//记录最近一次加入A中的活动

for (int i=2;i<=n;i++)//依次检查活动i是否与当前已选择的活动相容

{

if (s[i]>=f[j])

{

A[i]=true;

j=i;

}

else

{

A[i]=false;

}

}

}