Chương trình C cho bài toán Chọn hoạt động (Activity Selection Problem)

Bài toán chọn hoạt động: cho một tập hợp hoạt động với thời gian bắt đầu và kết thúc. Tìm tập con lớn nhất các hoạt động một người có thể thực hiện, mỗi lần chỉ làm một hoạt động.

Sử dụng tham lam (greedy algorithm) để chọn hoạt động tiếp theo. Thuật toán tham lam tìm giải pháp từng bước, mỗi bước chọn lựa chọn tốt nhất tại thời điểm đó dẫn đến giải pháp tối ưu toàn cục.

Lưu ý: Tham lam không áp dụng được cho mọi bài toán (ví dụ: 0-1 knapsack).

Thuật toán

Các thuật toán tham lam tiêu biểu:

1) Dijkstra - Đường đi ngắn nhất
2) Minimum Spanning Tree (Prim, Kruskal)
3) Huffman coding

Bài toán chọn hoạt động: cho n hoạt động với thời gian bắt đầu và kết thúc. Chọn số lượng hoạt động tối đa có thể thực hiện.

Ví dụ 3 hoạt động đã sắp xếp theo thời gian kết thúc:

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

Người ta có thể làm tối đa 2 hoạt động: [0, 2].

Ví dụ mã nguồn

#include <stdio.h>

int main() {
    int start[] = {1, 5, 12};
    int finish[] = {10, 13, 23};
    int n = sizeof(start) / sizeof(start[0]);
    int i, j;

    printf("Cac hoat dong duoc chon: ");
    i = 0;
    printf("%d\t", i);

    for (j = 1; j < n; j++) {
        if (start[j] >= finish[i]) {
            printf("%d ", j);
            i = j;
        }
    }
    return 0;
}

Kết quả đầu ra

Cac hoat dong duoc chon: 0 2