Bài toán có thể được diễn đạt lại thành việc chọn càng nhiều bộ ba càng tốt dưới ràng buộc rằng mỗi phần tử chỉ được sử dụng tối đa một lần.

Ta sẽ giả sử rằng \(A_1 \le ... \le A_N, B_1 \le ... \le B_N, C_1 \le ... \le C_N\) (Ta có thể sắp xếp chúng).

Ta có \(3\) nhận xét như sau:

Nhận Xét (1)

• Ta luôn chọn \(A_1\).

Chứng Minh: Giả sử rằng tồn tại một giải pháp tối ưu chọn một hoặc nhiều bộ ba \((A,B,C)\) mà không sử dụng \(A_1\). Chúng ta có thể thay thế một trong các bộ ba đã chọn trong một giải pháp tối ưu như vậy, có nghĩa là thay \((A_i, B_j, C_k)\) bằng \((A_1, B_j, C_k)\). Điều này không thay đổi số lượng bộ ba đã chọn, vì vậy một giải pháp tối ưu vẫn là một giải pháp tối ưu. Vì vậy ta có thể thấy rằng tồn tại một giải pháp tối ưu mà ta chọn \(A_1\).

Từ đó, chúng ta chỉ cần xem xét trường hợp \(A_1\) được chọn.

Nhận Xét (2)

Chúng ta không thể sử dụng \(B_j\) sao cho \(B_j \le A_1\). Vì vậy ta có thể xóa các B_j này từ đầu và tiếp tục.

Trường hợp \(B\) rỗng là khả năng rất hiếm xảy ra, vì vậy hãy giả sử ngược lại. Nghĩa là ta giả sử \(A_1 < B_1\).

Chúng ta có thể chứng minh rằng khẳng định sau đây đúng:

• Ta luôn chọn \(A_1\) và \(B_1\).

Chứng Minh: Giả sử rằng tồn tại một giải pháp tối ưu chọn một hoặc nhiều bộ ba \((A,B,C)\) mà không sử dụng \(A_1 và B_1\). Tương tự như chứng minh trong (1), chúng ta có thể chứng minh rằng tồn tại một giải pháp tối ưu sử dụng cả \(A_1\) và \(B_1\) trong một số bộ ba. Giả sử rằng \(A_1\) và \(B_1\) không nằm trong cùng một bộ ba và chúng thuộc về các bộ ba \((A_1, B_j, C_k)\) và \((A_1, B_j, C_k')\) tương ứng. Ta có thể sắp xếp lại các bộ ba này thành \((A_1, B_j, C_k')\) và \((A_1, B_j, C_k)\).

Nhận Xét (3)

Chúng ta không thể sử dụng \(C_k\) sao cho \(C_k \le B_1\). Vì vậy ta có thể xóa các \(B_j\) này từ đầu và tiếp tục giả sử \(A_1 < B_1 < C_1\).

Tương tự như nhận xét (1) và (2), chúng ta có thể chứng minh như sau:

• Ta luôn sử dụng \(A_1\) và \(B_1\) và \(C_1\) trong cùng một bộ ba.

Lời Giải

Với \(3\) nhận xét trên, ta sẽ tham lam theo vòng lặp như sau:

• Nếu \(A\) rỗng thì dừng vòng lặp, ngược lại ta cho \(A_1\) là giá trị nhỏ nhất trong \(A\) và xóa tất cả \(B_j\) không lớn hơn \(A_1\).
• Nếu \(B\) rỗng thì dừng vòng lặp, ngược lại ta cho \(B_1\) là giá trị nhỏ nhất trong \(B\) và xóa tất cả \(C_k\) không lớn hơn \(B_1\).
• Nếu \(C\) rỗng thì dừng vòng lặp, ngược lại ta cho \(C_1\) là giá trị nhỏ nhất trong \(C\).
• Ta tăng biến kết quả lên \(1\) đơn vị và xóa \(A_1, B_1, C_1\) và quay về để tiếp tục vòng lặp.

Độ phức tạp cho thuật toán này là \(O(NlogN)\) vì ta cần sắp xếp chúng theo thứ tự tăng dần.