活動選擇問題的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

以上是活動選擇問題的C程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！