Aktivite seçimi problemi, her biri bir başlangıç zamanı (s) ve bitiş zamanı (f) ile işaretlenmiş bir dizi faaliyet göz önüne alındığında, belirli bir zaman çerçevesi içinde çelişmeyen faaliyetlerin seçimiyle ilgili bir kombinatoryal optimizasyon problemidir. Sorun, bir kişinin bir seferde tek bir etkinlikte çalışabileceğini varsayarak, tek bir kişi veya makine tarafından gerçekleştirilebilecek maksimum etkinlik sayısını seçmektir.
Optimizasyon problemlerinin önüne geçmek için sıkça kullanılan algoritmalardır. Her zaman en bariz ve anında fayda sağlayan bir sonraki parçayı seçer.
#include <stdio.h>
#include <malloc.h>
void ActivitySelection(int *s, int *f, int n, int *sol)
{
sol[0] = 0;
int i, c = 0;
for(i = 1; i < n; i++)
if(f[sol[c]] <= s[i])
sol[++c] = i;
sol[++c] = -1;
}
void main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
int *sol = malloc(sizeof(int)*n);
ActivitySelection(s, f, n, sol);
int i;
for(i = 0; sol[i] != -1; i++)
printf("%dt%dt%dn", sol[i], s[sol[i]], f[sol[i]]);
}
Her biri bir başlangıç zamanı s ve bitiş zamanı f ile temsil edilen n aktivite bulunduğunu varsayalım. S ≥ f veya s ≥ f ise iki etkinlik i ve j’nin çelişkili olmadığı söylenir. Aktivite seçim problemi, çelişkili olmayan faaliyetlerin maksimum çözüm setini (S) bulmaktan ibarettir veya daha kesin bir ifadeyle, |S'| > |S| Birden fazla maksimal çözümün eşit ebatlara sahip olması durumundadır..