Caricamento efficiente del bus

Questo è (un po ') un esempio del problema dell'imballaggio del contenitore, che è spesso confuso con il problema dello zaino. Nell'imballaggio del contenitore, si dispone di contenitori di una certa capacità e si sta tentando di distribuire oggetti di varie dimensioni nei raccoglitori. L'idea è di utilizzare il minor numero possibile di contenitori.

Non stai esattamente cercando di minimizzare il numero di contenitori, però, stai cercando di minimizzare il numero di posti vuoti. Ed è possibile che tu stia cercando di minimizzare il numero di posti vuoti attraverso la flotta, cioè, hai quattro gruppi di tour di varie dimensioni, e vuoi accoglierli tutti con il minor numero di posti vuoti. Non riesco a pensare a un'istanza giusta, ma immagino che potrebbe essere possibile costruire una flotta e un gruppo di gruppi di tour in modo tale da farti stare meglio con una soluzione scadente per qualche gruppo perché ti ha permesso di evitare usando una soluzione ancora peggiore per qualche altro gruppo.

Diventa peggio. Che cosa succede se hai 20,30 e 50 autobus passeggeri. Ognuno usa diverse quantità di carburante, ma è più efficiente eseguire un 50 di quanto non sia per eseguire un 20 e un 30. Ma dalla nostra singola misura (il minor numero di posti vuoti), ha senso correre per un 50 tour dei passeggeri.

Inoltre, gli autobus con numeri strani, come 28 o 39, potrebbero distorcere molte delle nostre scorciatoie.

Quindi, a seconda della complessità della situazione, potresti fare una delle due cose:

Primo ed esauriente albero di ricerca: usa ogni possibile combinazione di bus. Se hai solo 3 o 4 dimensioni del bus, questa è probabilmente una soluzione ragionevole. Altrimenti, qualcosa come la riduzione del fit fit produrrebbe risultati ragionevoli, ma non ottimali.

Ecco una soluzione rapida e sporca in Python:

def add50(passengers, buses):
    proposed = buses + [50]
    if sum(proposed) < passengers:
        return add50(passengers, proposed)
    return proposed

def add30(passengers, buses):
    proposed = buses + [30]
    if sum(proposed) < passengers:
        proposed30 = add30(passengers, proposed)
        proposed50 = add50(passengers, proposed)
        return proposed30 if sum(proposed30) < sum(proposed50) else proposed50
    return proposed

print add30(88, [])
print add30(75, [])
print add30(105, [])

Quando lo eseguo, ottengo:

[30, 30, 30]
[30, 50]
[30, 30, 50]

Il codice sta eseguendo una ricerca approfondita attraverso gli scenari possibili. Poiché l'ordine non ha importanza ( [30, 50] è uguale a [50, 30] ), possiamo rendere lo spazio di ricerca molto più piccolo aggiungendo solo bus della stessa dimensione o più grandi. Ecco perché add30() può chiamare add50() , ma non viceversa.

Ho intenzione di rispondere a questa domanda dal punto di vista del cliente. Non vorrei un algoritmo hard coded per questa applicazione. Ci sono troppe variabili che possono cambiare nel tempo. Sebbene nulla sui tuoi autobus possa cambiare il peso dei fattori potrebbe cambiare o potrebbero essere scoperti nuovi fattori a cui non ho mai pensato (ad es. Tempo eccessivo, leggi e altri costi di guida).

Per questo motivo, vorrei essere in grado di creare la mia tabella di ricerca in base a una gamma del numero di passeggeri richiesto e vorrei creare le mie impostazioni per le migliori combinazioni di bus. Esempio: 31-50 = 1 X 50, 51-60 = 2 X 30. Questo deve davvero essere calcolato? È più facile cambiare le impostazioni rispetto a un mucchio di formule per il factoring di sedili, gas e autisti. Scopri la migliore combinazione e fai tutto ciò e avrai a disposizione un ampio spazio per modificare queste impostazioni come meglio credono.

Nuovi fattori potrebbero essere scoperti. Gli autobus più grandi pagano un tasso esponenzialmente più alto sui pedaggi? Posso ottenere conducenti meno costosi per i piccoli autobus quando una nuova legge per la certificazione e le licenze extra sale sugli autisti di autobus di oltre 30 passeggeri?

Assumono un nuovo consulente con una logica diversa rispetto alla formula e la tua app potrebbe dover essere riscritta. Vuoi dire che devi calcolare il costo del parcheggio?