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

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho n hoạt động với thời gian bắt đầu và kết thúc. Chọn số hoạt động tối đa 1 người có thể làm (chỉ làm 1 việc tại 1 thời điểm).

Ký hiệu: N - tổng hoạt động, S - mảng thời gian bắt đầu, F - mảng thời gian kết thúc.

# Cách tham lam (Greedy)

Ví dụ

def Activities(s, f):
    n = len(f)
    print("Các hoạt động được chọn:")
    i = 0
    print(i, end=" ")
    for j in range(n):
        if s[j] >= f[i]:
            print(j, end=" ")
            i = j

s = [1, 2, 0, 3, 2, 4]
f = [2, 5, 4, 6, 8, 8]
Activities(s, f)

Kết quả

Các hoạt động được chọn: 0 1

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python bài toán chọn hoạt động.