Program C untuk masalah pemilihan aktiviti

Masalah pemilihan aktiviti adalah masalah memandangkan satu set aktiviti dan masa mula dan tamatnya. Kita perlu mencari semua aktiviti yang boleh dilakukan oleh seseorang dengan melakukan satu aktiviti sekali gus.

Masalah ini menentukan algoritma tamak untuk memilih aktiviti seterusnya untuk dilakukan. Mari kita fahami algoritma tamak dahulu.

Algoritma Greedy ialah algoritma yang cuba mencari penyelesaian kepada masalah dengan mencari penyelesaian langkah demi langkah. Untuk memilih langkah seterusnya, algoritma juga memilih langkah yang kelihatan paling menjanjikan, iaitu langkah yang segera membawa kepada penyelesaian yang dioptimumkan berbanding yang lain. Algoritma tamak digunakan untuk menyelesaikan masalah pengoptimuman kerana ia cuba mencari penyelesaian yang paling optimum untuk langkah perantaraan seterusnya, yang membawa kepada penyelesaian optimum kepada keseluruhan masalah.

Walaupun algoritma tamak adalah penyelesaian yang baik, terdapat beberapa masalah yang menghalangnya daripada digunakan. Sebagai contoh, ransel 0-1 tidak boleh diselesaikan menggunakan algoritma tamak.

Algoritma

Sesetengah algoritma tamak standard ialah -

1) Dijkstrata’s Shortest Path
2) Minimum Spanning Tree (MST) {prim’s and kruskal’s}
3) Huffman coding

Masalah pemilihan tidak aktif, kami diberi n masalah dengan masa mula dan tamat. Kita perlu memilih bilangan maksimum aktiviti yang boleh dilakukan oleh seseorang, dengan mengandaikan bahawa dia hanya boleh melakukan satu aktiviti pada satu masa.

Terdapat 3 aktiviti disusun mengikut masa tamat mereka,

Start = [1 , 5 , 12 ]
End = [10, 13, 23]

Di sini seseorang boleh melakukan sehingga dua aktiviti. Aktiviti yang boleh dilakukan ialah [0, 2].

Contoh

Demonstrasi

#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;
}

Output

Following activities are selected 0 2

Atas ialah kandungan terperinci Program C untuk masalah pemilihan aktiviti. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!