โปรแกรม C สำหรับปัญหา Activity Selection (Greedy Algorithm)

ปัญหา Activity Selection คือปัญหาที่ให้ชุดกิจกรรมพร้อมเวลาเริ่มต้นและเวลาสิ้นสุด ต้องหากิจกรรมสูงสุดที่บุคคลทำได้ โดยทำกิจกรรมเดียวในเวลาเดียวกัน

ใช้ Greedy Algorithm (อัลกอริทึมลืม) เลือกกิจกรรมถัดไปที่ดูมีศักยภาพมากที่สุด นำไปสู่ optimal solution

Greedy Algorithm หาคำตอบทีละขั้นตอน เลือกขั้นตอนที่ดูดีที่สุดในขณะนั้น ใช้แก้ปัญหา optimization แต่ไม่ใช่ทุกปัญหา (เช่น 0-1 knapsack)

อัลกอริทึม

1) Dijkstra's Shortest Path
2) Minimum Spanning Tree (Prim's, Kruskal's)
3) Huffman coding

ใน Activity Selection: กำหนด n กิจกรรม พร้อมเวลาเริ่มและสิ้นสุด เลือกกิจกรรมสูงสุดที่ทำได้ (ทำทีละอย่าง)

ตัวอย่าง 3 กิจกรรม เรียงตามเวลาสิ้นสุด:

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

บุคคลทำได้สูงสุด 2 กิจกรรม คือ [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