Thuật toán tốt nhất để mời mọi người tham gia

Question

Tôi mới ở đây nhưng đã tìm thấy câu hỏi trong sách giáo khoa của tôi. Thật không may nó không có câu trả lời vì vậy tôi đã tự hỏi nếu ai đó có thể xin vui lòng giúp đỡ. Câu hỏi là:

Bạn có nhiệm vụ truyền bá lời mời trong công ty. Bạn chỉ có thời gian để nói chuyện với một số người nhất định, nhưng bạn được đảm bảo rằng nếu bạn mời ai đó, họ sẽ mời ông chủ của họ, người đó sẽ mời ông chủ của họ, v.v., tất cả các con đường đến CEO. Bạn đã vạch ra toàn bộ hệ thống phân cấp công ty và chỉ định giá trị cho mỗi người, cho biết mức độ mời họ có giá trị. Với thiết lập này và giới hạn về số người bạn có thể nói chuyện, bạn muốn tính toán số lượng tối ưu tập hợp những người được mời. Một nhóm người tối ưu sẽ tối đa hóa tổng giá trị của tất cả những người được mời, trực tiếp hoặc gián tiếp, theo lựa chọn của bạn.

Sẽ có chính xác một người, Giám đốc điều hành, không có ông chủ trong hệ thống phân cấp. Tất cả những người khác cuối cùng sẽ trả lời người này trong chuỗi lệnh, nhưng không nhất thiết phải trực tiếp .

Bạn được đảm bảo rằng mỗi người sẽ có tối đa một ông chủ, nhưng ông chủ đó có thể có một lần lượt khác. Ví dụ, người A có thể có một ông chủ B, có ông chủ là C, có ông chủ là D, có ông chủ là Giám đốc điều hành. Do đó ảnh hưởng đến người A sẽ tự động ảnh hưởng đến B, C, D và CEO.

Các nhân viên khác nhau có thể có các điểm chung trong chuỗi lệnh. Bạn KHÔNG nhận thêm giá trị để ảnh hưởng đến một người nhiều lần. Ví dụ: nếu A và B trả lời trực tiếp cho Giám đốc điều hành và bạn ảnh hưởng cả hai, bạn sẽ nhận giá trị val (A) + val (B) + val (CEO), chứ không phải val (A) + val (B) + 2val (Giám đốc điều hành).

Cho số nguyên dương j, chọn j người mà cuối cùng sẽ cho kết quả là trong giá trị tổng thể lớn nhất.

Tôi biết rằng phương pháp tiếp cận vũ lực là chỉ tìm kiếm danh sách cho giá trị lớn nhất j lần, nhưng điều đó không hữu ích lắm. Tôi nghĩ rằng có một phương pháp lập trình động nhưng nỗ lực của tôi không phải lúc nào cũng cung cấp câu trả lời đúng. Bất kỳ trợ giúp sẽ được đánh giá cao!

Answer 1

Cho phép V [e, k] là giá trị lớn nhất của việc gửi thư mời đến cấp dưới trực tiếp và gián tiếp của e và e, bỏ qua giá trị của tất cả các giám sát viên trực tiếp và gián tiếp của e. Nếu nhân viên e không có người cấp dưới, sau đó các trường hợp cơ bản là

V[e, k], k = 0 = 0 
V[e, k], k > 0 = val(e). 

Nếu nhân viên e0 có hai cấp dưới, e1 và e2, sau đó tái phát là

V[e0, k], k = 0 = 0 
V[e0, k], k > 0 = max over j of val(e0) + V[e1, j] + V[e2, k - j]. 

Các chập ngây thơ với hơn hai nhân viên là quá chậm, vì vậy chúng ta phải xoay chuyển cặp đầu tiên và sau đó xoay chuyển trong phần còn lại. Tôi sẽ bỏ qua các chi tiết.

Answer 2

Chỉnh sửa: câu trả lời này giả định các giá trị để mời mọi người đều không âm.

Sự cố này có thể được giải quyết bằng thuật toán tham lam. Đầu tiên chúng ta hãy thảo luận về trường hợp các giá trị bằng nhau, vì vậy chúng tôi chỉ cố gắng mời số lượng người tối đa.Quan sát chính là trong bất kỳ giải pháp tối ưu nào, bạn luôn nên chọn người có số lượng cấp trên trực tiếp hoặc gián tiếp lớn nhất. Dưới đây là giải thích ngắn gọn về lý do: giả sử người X có cấp trên cao nhất và bạn có một số lựa chọn không bao gồm người X. Hãy xem xét người đó Y trong số các lựa chọn của bạn chia sẻ cấp trên cao nhất với X. Sau đó, bạn có thể làm tốt hơn bằng cách chọn X thay vì Y.

Vì vậy, trong bước đầu tiên, chúng tôi luôn có thể tham lam chọn người có cấp trên cao nhất. Sau đó, vấn đề giảm xuống cùng một vấn đề trên một số cây nhỏ hơn. Ví dụ, giả sử chúng ta đang chọn 3 khách mời từ các cây sau:

 A 
    B  C 
D E F G 
H I J K L M N O 

lựa chọn đầu tiên của chúng tôi sẽ H, tự động cho chúng ta D, B, và A. Sau đó, nó vẫn còn để chọn 2 từ ba cây

I E  C 
    J K F G 
     L M N O 

Lựa chọn tốt nhất tiếp theo là L, v.v.

Chúng ta có thể làm điều này một cách hiệu quả, bởi vì chúng ta chỉ cần theo dõi đứa trẻ sâu nhất (không nhất thiết là con trực tiếp) của mỗi nút, mà chúng ta có thể tính toán trước. Sau đó, chúng tôi cần một số loại cấu trúc dữ liệu xếp hàng ưu tiên để chọn cây tốt nhất để chọn. Nếu bạn đang chọn k những người từ một hệ thống phân cấp có kích thước n, điều này sẽ cung cấp thuật toán O(n + k log n).

Để mở rộng trường hợp giá trị có thể không bằng nhau, về cơ bản ý tưởng chính xác giống nhau, ngoại trừ thay vì chiều sâu, bạn cần tính tổng giá trị của tất cả cấp trên. Đối với mỗi nút X, bạn theo dõi đứa trẻ Y có tổng giá trị lớn nhất dọc theo đường dẫn giữa Y và X.

Answer 3

Âm thanh như graph problem. Bạn có thể sử dụng ý tưởng về các thành phần được kết nối để nhận ra một giải pháp cho điều này.

• Lần lặp đầu tiên sẽ bao gồm tất cả mọi người trong công ty nơi bạn sẽ xác định CEO là ai và trực tiếp bên dưới anh ấy.
• Đưa từng tên trùm trực tiếp bên dưới Giám đốc điều hành dưới dạng tập hợp thành phần ban đầu.
• Sau đó, đối với mỗi người khác, bạn sẽ sử dụng dfs để liên kết chúng với một ông chủ cấp 2 (Đây là cách tiếp cận năng động).
• Bạn muốn làm điều này phần cuối theo cách mà nếu person F là ông chủ của person E, người lần lượt là ông chủ của person D, ... tất cả các con đường xuống person A, sau đó bạn muốn sau khi dfs được có thể nói trong O (1) thời gian mà người F là ông chủ của người A và ngược lại.

Hãy nhớ giữ số đếm cho mỗi sếp nơi số sẽ là tổng giá trị của tất cả mọi người bên dưới anh ấy và tùy ý theo dõi số lượng người.

Trường hợp tối ưu là bạn sẽ tìm thấy tất cả mọi người trong chuỗi trước, nếu không thuật toán sẽ chạy trong O (nk) trong đó k là chuỗi tối đa từ dưới lên trên