数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学活动选择问题的C语言程序
活动选择问题是指，我们得到一组活动及其开始和结束时间。我们需要找到一个人可以在同一时间只执行一项活动的情况下能够执行的所有活动。
此问题中采用贪婪算法来选择下一个要执行的活动。让我们首先了解一下**贪婪算法**。
**贪婪算法**是一种试图通过逐步寻找问题的解决方案来找到问题的解决方案的算法。为了选择下一步，该算法还会选择看起来最有希望的步骤，即与其他步骤相比，该步骤可以立即得到最佳的解决方案。贪婪算法用于解决优化问题，因为它试图为下一步找到最佳解决方案，从而导致整个问题的最佳解决方案。
虽然贪婪算法是一个很好的解决方案，但有些问题是无法应用它的。例如，0-1背包问题就无法使用贪婪算法解决。
算法
一些标准的贪婪算法是：
1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding在活动选择问题中，我们得到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
更新于：2020年1月3日
5000+ 次浏览
广告