資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告