c++贪心算法经典例题.docxVIP

c++贪心算法经典例题和详解

贪心算法（GreedyAlgorithm）是一种优化问题解决方法，其基本思想是每一步都选择当前状态下的最优解，以期望达到全局最优解。贪心算法的特点是每一步都要做出一个局部最优的选择，而这些局部最优选择最终构成了全局最优解。

下面是一个经典的贪心算法例题以及详解：

例题：活动选择问题（ActivitySelectionProblem）

假设有一个需要在同一时段使用同一个资源的活动集合，每个活动都有一个开始时间和结束时间。设计一个算法，使得能够安排最多数量的互不相交的活动。

#输入：

-活动的开始时间数组`start[]`。

-活动的结束时间数组`end[]`。

#输出：

-选择的互不相交的活动的最大数量。

#算法详解：

1.首先，将活动按照结束时间从小到大排序。

2.选择第一个活动，并将其加入最终选择的集合中。

3.对于剩下的活动，选择下一个结束时间最早且与前一个活动不冲突的活动。

4.重复步骤3，直到所有活动都被选择。

```cpp

#includeiostream

#includealgorithm

#includevector

usingnamespacestd;

//定义活动结构体

structActivity{

intstart,end;

};

//比较函数，用于排序

boolcompareActivities(Activitya,Activityb){

returna.endb.end;

}

//贪心算法解决活动选择问题

voidactivitySelection(vectorActivityactivities){

//按照结束时间排序

sort(activities.begin(),activities.end(),compareActivities);

//第一个活动总是被选中

coutSelectedactivity:(activities[0].start,activities[0].end)endl;

//选择其余活动

intlastSelected=0;

for(inti=1;iactivities.size();i++){

//如果当前活动的开始时间大于等于上一个选择的活动的结束时间，则选择该活动

if(activities[i].start=activities[lastSelected].end){

coutSelectedactivity:(activities[i].start,activities[i].end)endl;

lastSelected=i;

}

}

}

intmain(){

vectorActivityactivities={{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};

coutActivitiesbeforesorting:endl;

for(constActivityactivity:activities){

cout(activity.start,activity.end);

}

coutendl;

activitySelection(activities);

return0;

}

```

在这个例子中，我们首先定义了一个活动的结构体`Activity`，然后编写了一个比较函数`compareActivities`用于排序。主函数中，我们创建了一个包含活动的数组，输出了排序前的活动，然后调用`activitySelection`函数进行贪心选择。选择结果是安排的互不相交的最大数量的活动。

贪心算法的思路是通过每一步的局部最优选择来达到全局最优，适用于一些问题，但并不是所有问题都适合贪心算法。在实际应用中，需要仔细分析问题的性质来判断是否可以使用贪心算法。