活动选择问题的 C 程序
cserver side programmingprogramming更新于 2024/11/4 20:42:00
活动选择问题是指我们给定一组活动及其开始和结束时间的问题。我们需要找到一个人一次可以执行的所有这些活动。
贪婪算法在此问题中被指定用于选择要执行的下一个活动。让我们首先了解贪婪算法。
贪婪算法是一种通过逐步寻找解决方案来尝试找到问题解决方案的算法。为了选择下一步，算法还选择了看起来最有希望的步骤，即与其他步骤相比可以立即产生优化解决方案。贪婪算法用于解决优化问题，因为它试图为下一个中间步骤找到最优化的解决方案，从而得到整个问题的最优解。
虽然贪婪算法是一个很好的解决方案，但也有一些问题不能应用。例如，0-1背包不能用贪婪算法解决。
算法
一些标准的贪婪算法是−
1) Dijkstrata 的最短路径
2) 最小生成树 (MST) {prim 和 kruskal}
3) 霍夫曼编码
不活动选择问题，我们给出了 n 个具有开始和结束时间的问题。并且，我们需要选择一个人在某个时间点可以执行的最大活动数量，前提是他可以在某个时间点执行单个活动。
有 3 项活动按完成时间排序，
Start = [1 , 5 , 12 ] End = [10, 13, 23]
此处，该人最多可以执行两项活动。可以执行的活动是 [0, 2]。
示例
#include<stdio.h>
int main(){
int start[] = {1 , 5 , 12};
int finish[] = {10, 13, 23};
int activities = sizeof(start)/sizeof(start[0]);
int i, j;
printf ("Following activities are selected \t");
i = 0;
printf("%d\t", i);
for (j = 1; j < activities; j++){
if (start[j] >= finish[i]){
printf ("%d ", j);
i = j;
}
}
return 0;
}
输出
Following activities are selected 0 2
