Puzzle di programmazione con selezione costante

Question

Puzzle di programmazione con selezione costante

#1 da (0 voti)

2

LA DOMANDA:

C'è un evento in cui ci sono N concorrenti. Ci sono tre compiti nell'evento: A, B, C (per esempio). Ogni partecipante prende parte agli eventi nell'ordine elencato: un concorrente deve prima completare A e B prima di iniziare C.

Tuttavia, nell'evento A può partecipare solo una persona alla volta. Qualsiasi numero di persone può partecipare contemporaneamente a B e C.

Quindi l'evento funziona come segue. Al momento 0, il primo concorrente inizia A, mentre i restanti cittadini attendono che la prima persona finisca. Non appena la prima persona ha finito, lui o lei procede all'evento B, e il secondo cittadino inizia A. In generale ogni volta che una persona completa A, la persona successiva inizia A. Ogni volta che una persona ha finito con A, lui o lui lei procede immediatamente verso B, indipendentemente da ciò che fanno gli altri concorrenti. L'intero evento termina non appena tutti i concorrenti finiscono tutti e 3 gli eventi.

Quindi alla domanda di base viene dato il numero di partecipanti N e il tempo impiegato da ciascuna persona per ciascuno dei 3 eventi, calcolare il tempo minimo in cui l'intero evento potrebbe essere completato.

IL MIO TENTATIVO:

Questo è l'algoritmo che ho trovato:

LeastTime (persone (2d array [n] [3] con il tempo di ogni persona per ogni evento, n, front_chosen = false)

    The least time for n people can be broken up into 2 cases:
    1. The current guy seated first for event A
        1.1 We take t1_1 -> time for current guy in event A + time taken for the rest of the people to finish the whole event with the front taken
        1.2 We take t1_2 -> time for current guy in event A + time for his remaining events
        1.3 The time taken for the whole event in this case is t1 = max{t1_1,t1_2}. 

    2 The current guy is not seated first for event A
        2.1 We modify people such that the first element is placed last
        2.2 t2 -> LeastTime(people, n, false)
    3. We return min {t1,t2}

Quindi è quello che mi è venuto in mente. Quali sono alcuni migliori soluzioni più efficienti? Anche le soluzioni alternative saranno utili.

algorithms problem-solving dynamic-programming

posta Akshay Tiwary 13.09.2013 - 17:29

fonte

1 risposta

Leggi altre domande sui tag algorithms problem-solving dynamic-programming

Abbinamento efficace e semplice per 2 insiemi di punti su scala ridotta Avere i miei oggetti così consapevoli di ogni interconnessione è una cosa brutta?

score 0 · Accepted Answer

Dato il tempo impiegato da tutti i partecipanti in tutti gli eventi, il tempo trascorso sull'evento A è invariato; pertanto, la durata dell'evento globale più breve può essere trovata concentrandosi sulla persona che è più lenta alla combinazione di B + C e ottimizzando l'evento A per massimizzare la sovrapposizione tra (B + C) tempo e (A) tempo.

Riorganizza l'input in persona [n] [2] dove il tempo della persona N sull'evento A è di persona [N] [1] e la loro ora sugli eventi B e C combinati è di persona [N] [2].

Ordina decrescente sulla colonna 2 e quindi sulla colonna 1.

Il momento in cui ogni persona finisce è quindi la somma di tutte le A fino a includere la propria A, più la loro BC.

Il momento in cui termina l'evento è il massimo dei tempi di completamento.

es. per le persone che hanno momenti di:

(A,B,C)
[1,2,3]
[2,2,2]
[1,5,6]
[5,1,1]
[4,5,6]

riorganizza in:

(A,(B+C))
[1,5]
[2,4]
[1,11]
[5,2]
[4,11]

ordina in:

[4,11]
[1,11]
[1,5]
[2,4]
[5,2]

Quindi i tempi di fine sono:

4 + 11                 = 15
4 + 1 + 11             = 16
4 + 1 + 1 + 5          = 11
4 + 1 + 1 + 2 + 4      = 12
4 + 1 + 1 + 2 + 5 + 2  = 15

E il completamento più rapido possibile dell'evento è di 16 minuti.