Tutorial — Largest Compatible Team Selection

Bài toán yêu cầu chọn ra một nhóm tình nguyện viên đông nhất sao cho không có hai người nào mâu thuẫn với nhau. Khi mô hình hóa mỗi người là một đỉnh và mỗi cặp mâu thuẫn là một cạnh của đồ thị, yêu cầu này tương đương với việc tìm một tập độc lập có kích thước lớn nhất.

Do số lượng tình nguyện viên $n$ không vượt quá $16$, tổng số tập con có thể tạo thành chỉ là $2^n \le 2^{16} = 65536$. Một tập hợp là hợp lệ khi và chỉ khi mọi tập con của nó đều hợp lệ và việc thêm một thành viên mới không tạo ra bất kỳ mâu thuẫn nào với các thành viên hiện có.

Ta có thể sử dụng quy hoạch động trên mặt nạ bit với mảng boolean $\text{valid}[mask]$ để kiểm tra tính hợp lệ của từng tập con theo thứ tự tăng dần của giá trị mặt nạ. Với mỗi mặt nạ hợp lệ, ta cập nhật kích thước lớn nhất và duyệt các bit bật để xuất tên các thành viên theo đúng thứ tự từ điển.