Cặp ghép Lớp các bài toán xác định một tương ứng giữa hai tập phần tử A và B cho trước, thí dụ như tập A gồm các em thiếu nhi và tập B gồm các món quà như trong bài toán Chị Hằng dưới đây được gọi là các bài toán cặp ghép và thường được kí hiệu là f: | Chương 3 Cặp ghép Lớp các bài toán xác định một tương ứng giữa hai tập phần tử A và B cho trước thí dụ như tập A gồm các em thiếu nhi và tập B gồm các món quà như trong bài toán Chị Hằng dưới đây được gọi là các bài toán cặp ghép và thường được kí hiệu là f A B với ý nghĩa là cần xác định một ánh xạ tức là một phép đặt tương ứng mỗi phần tử i của tập A với duy nhất một phần tử j của tập B f i j. Một trong các thuật toán giải các bài toán này có tên là thuật toán Ghép cặp. Thuật toán đòi hỏi thời gian tính toán là phép so sánh trong đó n là số phần tử lực lượng của tập A m là số phần tử của tập B n A m B . Chương này trình bày thuật toán ghép cặp và các biến thể của nó. Chị Hằng Nhân dịp Tết Trung Thu Chị Hằng rời Cung Trăng mang m món quà khác nhau mã số đến vui Trung Thu với n em nhỏ mã số tại một làng quê. Trước khi Chị Hằng phát quà mồi em nhỏ đã viết ra giấy những món quà mà em đó mơ ước. Yêu cầu giúp Chị Hằng chia cho mồi em đúng 1 món quà mà em đó yêu thích. Dữ liệu vào file văn bản Dòng đầu tiên hai số n m Dòng thứ i trong số n dòng tiếp theo k b1 b2 . bk - k là số lượng quà em i yêu thích b1 b2 . bk là mã số các món quà em i yêu thích. Dữ liệu ra file văn bản Dòng đầu tiên v - số em nhỏ đã được nhận quà. v dòng tiếp theo mồi dòng 2 số i b cho biết em i được nhận món quà b. Thí dụ Ý nghĩa 5 5 5 Có 5 em và 5 món quà. Em 1 thích 2 món quà 1 và 5 em 2 thích 2 2 1 5 1 1 món quà 2 và 4 em 3 thích 2 món quà 1 và 2 em 4 thích 3 món quà 2 2 4 2 4 1 4 và 5 em 5 thích 2 món quà 1 và 3. 2 1 2 3 2 Một phương án xếp em nhỏ quà như sau 1 1 2 4 3 2 4 5 3 1 4 5 4 5 5 3. 2 1 3 5 3 Thuật toán Giả sử các phần tử của tập nguồn A các em nhỏ được mã số từ 1 đến n và các phần tử của tập đích B các gói quà được mã số từ 1 đến m. Sau khi đọc dữ liệu và thiết lập được ma trận 0 1 hai chiều c với các phần tử c i j 1 cho biết em i thích món quà j và c i j 0 cho biết em i không thích quà j. Nhiệm vụ đặt ra là thiết lập một ánh xạ .
