Programmazione ottimale del film

-1

Diciamo che il signor A va al cinema e ottiene un programma di film. Oggi ci sono N film sul programma (1 < N < 50) e per ogni film il momento dell'inizio e l'ora della fine sono dati in minuti. Mr. A vuole vedere quanti minuti di film è possibile. Ma c'è una regola nel cinema: se un film inizia, non puoi guardarlo. In altre parole se il signor A guarda il film 1 e nel frattempo inizia il film 2, il signor A non può guardarlo. Trova il numero massimo di minuti che Mr. A può spendere guardando i film.

All'inizio ho ordinato i film in base alla loro ora di inizio. Quindi ho creato una matrice NxN e l'ho riempita con valori falsi. Ora se Film X e Film Y si intersecano, io gioco nello stesso tempo anche solo per un minuto, quindi Matrix [X] [Y] e Matrix [Y] [X] ottengono il valore vero. Poi controllo il caso quando ogni film è nella soluzione ottimale. Li ho messi in vettoriale. Ora usando la ricorsione, controllo tutte le combinazioni possibili. Se Movie X non ha un'intersezione con tutti i film del vettore, inserisco nel vettore, poiché non ci saranno intersezioni e quindi passerò al film successivo. E così via.

Questo algoritmo funziona, ma penso che sia troppo dispendioso in termini di tempo e, come voglio dire, è "brute-force modificata". C'è un modo migliore per raggiungere la soluzione ottimale.

NOTA: siamo interessati solo al numero massimo di minuti, non al numero massimo di film. Alla fine il programma dovrebbe stampare il numero massimo di minuti, non un elenco dei film che il signor A dovrebbe guardare.

    
posta Stefan4024 21.03.2014 - 01:15
fonte

1 risposta

1

Mi sembra un albero decisionale.

Crea un grafico.

Inizia con un nodo radice, quindi per i suoi figli elenca tutti i film che A potrebbe guardare prima.

Per ogni bambino, memorizza la lunghezza del film e aggiungi nodi per ogni film che A potrebbe guardare dopo che il film di quel bambino termina. (esci, esci dal teatro 7 alle 10:02 e controlla gli altri 49 cinema per vedere quali non stanno attualmente riproducendo un film. Aggiungi loro come nodi figli).

Continua fino a leggere la fine del giorno / il tuo grafico è completamente popolato.

Ora cerca nel grafico il percorso con i minuti collettivi più alti (vale a dire, la somma dei minuti per ciascun film nel percorso). Esistono diversi algoritmi noti per farlo . DFS mi viene in mente, ma penso che ce ne siano di migliori.

--------- ---------- Modifica

Eccellente commento di AMADANON Inc:

Potresti migliorare questo alogritmo: fai prima una ricerca per ampiezza, e in qualsiasi momento quando due o più rami NON stanno guardando un film contemporaneamente, tutti, tranne quello con il maggior numero di minuti visto fino a quel momento, possono essere eliminati (nel caso di parità nel numero di minuti, tutti tranne uno scelto arbitrariamente nel pareggio possono essere eliminati). Ciò farà risparmiare molte elaborazioni durante il festival del cortometraggio.

(I commenti sono a volte persi, quindi lo metto qui)

    
risposta data 21.03.2014 - 01:58
fonte

Leggi altre domande sui tag