Thuật toán Bartender lười biếng

Question

Tôi đã tìm thấy sự cố sau đây trong một trong các cuộc phỏng vấn. Xin vui lòng đề nghị tôi thuật toán cho việc này. Tôi không cần mã.

• Có N số đồ uống có thể. (N1, n2 ..)
• Có C số lượng khách hàng cố định.
• Mọi khách hàng đều đã cố định bộ đồ uống yêu thích.
• Bartender có để tạo ra số lượng ít nhất có thể các loại đồ uống để đủ cần của tất cả các khách hàng

Ví dụ:

Cust1: n3,n7,n5,n2,n9 
Cust2: n5 
Cust3: n2,n3 
Cust4: n4 
Cust5: n3,n4,n3,n5,n7,n4  

Output: 3(n3,n4,n5) 

Answer 1

Hãy tái cấu trúc vấn đề này. Chúng tôi có biểu đồ hai bên G(Drinks, Customers, E). Trường hợp cạnh e(i, j) là trong E khi uống i là trong bộ yêu thích của khách hàng j. Và chúng tôi muốn tìm tập hợp con số ít nhất là Drinks để bao gồm tất cả Customers được đặt.

Sự cố này là biến thể của Set cover problem (xem Hitting set formulation). Nó được biết là NP-hard, vì vậy không có thuật toán đa thức đã biết.

Tùy thuộc vào các ràng buộc của vấn đề cụ thể, nó có thể được giải quyết bằng thuật toán brute-force đơn giản hoặc phương pháp lập trình/ghi nhớ động, nhưng bạn nên biết các ràng buộc chính xác sau đó.