Algoritmo migliore per invitare le persone a festeggiare

Question

Sono nuovo qui, ma ho trovato una domanda nel mio libro di testo. Sfortunatamente non ha risposte quindi mi chiedevo se qualcuno potesse aiutarmi per favore. La domanda è:

Ti viene assegnato il compito di diffondere gli inviti all'interno di un'azienda. Hai solo il tempo di parlare con una certa quantità di persone, ma sei sicuro che se inviti qualcuno, inviteranno il loro capo, quella persona chiamerà il suo capo, , e così via, fino al AMMINISTRATORE DELEGATO. Hai mappato l'intera gerarchia aziendale e assegnato un valore a ogni persona, indicando quanto sarebbe utile invitarli. Data questa configurazione e un limite di sul numero di persone con cui puoi parlare, devi calcolare il gruppo di persone ottimale da invitare . Un gruppo ottimale di persone massimizzerà il valore totale di tutte le persone invitate, direttamente o indirettamente, dalla tua selezione.

Ci sarà esattamente una persona, l'amministratore delegato, senza capo nella gerarchia. Tutte le altre alla fine risponderanno a questa persona sulla catena di comando, ma non direttamente su .

È garantito che ogni persona avrà al massimo un capo, ma che il capo può avere un altro a sua volta. Ad esempio, la persona A potrebbe avere un capo B, il cui capo è C, il cui capo è D, il cui capo è l'amministratore delegato. Così influenzando la persona A sarà influenzare automaticamente B, C, D, e il CEO.

Diversi dipendenti possono avere capi in comune nella catena di comando. NON ottieni un valore aggiuntivo per influenzare una persona più di una volta. Ad esempio, se A e B rispondono direttamente all'Amministratore Delegato, e voi influenzate entrambi, riceverete un valore di val (A) + val (B) + val (CEO), non val (A) + val ( ). B) + 2val (CEO).

Dato un numero intero positivo j, selezionare le persone j che alla fine risulterebbero nel valore complessivo massimo.

So che l'approccio forza bruta consiste semplicemente nella ricerca dell'elenco per il valore massimo j volte, ma ciò non è molto utile. Penso che ci sia un approccio di programmazione dinamica, ma il mio tentativo non ha sempre fornito la risposta corretta. Qualsiasi aiuto sarebbe apprezzato!

Answer 1

Sia V [e, k] il valore massimo di emissione di k inviti a subordinati diretti ed indiretti di e ed e, ignorando il valore di tutti i supervisori diretti e indiretti di e. Se dipendente e non ha subordinati, allora il caso base è

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

se dipendente e0 ha due sottoposti, E1 ed E2, quindi la ricorrenza è

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

La convoluzione naive con più di due dipendenti è troppo lento, quindi dobbiamo convogliare la prima coppia e poi convolvi nel resto. Ho intenzione di omettere i dettagli.

Answer 2

Modifica: questa risposta presuppone che i valori per invitare le persone siano tutti non negativi.

Questo problema può essere risolto utilizzando un algoritmo avido. Vediamo prima di tutto il caso in cui i valori sono tutti uguali, quindi stiamo solo cercando di invitare il numero massimo di persone.L'osservazione chiave è che in qualsiasi soluzione ottimale, si dovrebbe sempre scegliere la persona con il maggior numero di superiori diretti o indiretti. Ecco una breve spiegazione del perché: supponiamo che la persona X abbia i superiori e che tu abbia alcune selezioni che non includono la persona X. Si consideri la persona Y tra le selezioni che condivide i più alti con X. Quindi, puoi fare meglio selezionando X anziché Y.

Quindi, nella prima fase, possiamo sempre selezionare avidamente la persona con i superiori. Quindi, il problema si riduce allo stesso problema su diversi alberi più piccoli. Ad esempio, supponiamo stiamo selezionando 3 invitati dal seguente albero:

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

La nostra prima selezione sarà H, che ci dà automaticamente D, B e A. Quindi, resta da selezionare 2 dai tre alberi

I E  C 
    J K F G 
     L M N O 

La migliore scelta successiva è L, e così via.

Possiamo farlo in modo efficiente, perché abbiamo solo bisogno di tenere traccia del bambino più profondo (non necessariamente figlio diretto) di ciascun nodo, che possiamo calcolare in anticipo. Quindi, abbiamo bisogno di una sorta di struttura dei dati delle code di priorità per selezionare la migliore struttura da cui prelevare. Se si seleziona k persone da una gerarchia di dimensioni n, questo dovrebbe fornire un algoritmo O(n + k log n).

Per estendere questo al caso in cui i valori possono essere non uguali, in pratica funziona esattamente la stessa idea, eccetto che in profondità, è necessario calcolare il valore totale di tutti i superiori. Per ogni nodo X, si tiene traccia del figlio Y che ha il valore totale più elevato lungo il percorso tra Y e X.

Answer 3

Suoni come un graph problem. È possibile utilizzare l'idea di componenti collegati per realizzare una soluzione a questo.

• La prima iterazione riguarderà tutti i membri dell'azienda in cui verrà determinato chi è l'amministratore delegato e chi è direttamente sotto di lui.
• Prendere ciascuno dei capi direttamente sotto il CEO come set iniziale di componenti.
• Quindi per l'altra persona, si utilizzerà dfs per associarli a un boss di secondo livello (questo è l'approccio dinamico).
• si vuole fare questa ultima parte in modo tale che se person F è il boss della person E, che a sua volta è il capo di person D, ... tutta la strada fino a person A, poi si desidera, dopo DFS per essere in grado di dire in O (1) volta che la persona F è il capo della persona A e viceversa.

Ricordarsi di tenere un conteggio per ogni capo in cui il conteggio sarà la somma dei valori di tutte le persone sotto di lui e, facoltativamente, tenere traccia del numero di persone.

Il caso ottimale sarebbe che trovi tutte le persone inferiore a catena prima, in caso contrario l'algoritmo deve essere eseguito in O (nk) dove k è la catena di massima dal basso verso l'alto