L'algoritmo giusto per ottenere una combinazione perfetta

Questo particolare problema è una variazione su un problema ben noto (e ben studiato) noto come problema di taglio delle scorte .

Nella classica definizione di questo problema, considera di avere ampi rotoli di prodotto di una certa larghezza. Hai bisogno di tagliarli in rotoli di larghezza inferiore con spreco minimo (e cambi di coltello):

Ilmotivopercuiquestoècosìbenstudiatoèchehaenormiimpattisuiprocessiindustrialiconanchepiccoliguadagnidiefficienza.Sipresentaincarta(rotolidicarta),film(rotolidipellicola)eindustriedimetalloconvariazioniinteressantiaggiuntiveperciascunodiessi(iltagliodellacartainformatoA4comportaduetaglisumacchinediversechepossonoaverespecifichediverse(unapiùeconomicaL'industriadelvetrohaunaltroproblemasimilenotocome problema di ghigliottina perché deve essere tagliato in pezzi rettangolari anziché funzionare con i rotoli.

Questo problema è anche equivalente al problema dello zaino.

Conoscendo queste cose, ci sono una serie di algoritmi diversi che tentano di risolvere questa classe di problemi che si sovrappongono a troppi simboli matematici funky, congetture e altri documenti.

Le risposte abbastanza buone sono possibili rapidamente, le risposte perfette richiedono molto tempo perché dovrai enumerare la maggior parte se non tutte le possibilità.

Ho fatto un po 'di lavoro in una classe di sistemi operativi universitari sull'assegnazione di blocchi di memoria con file di dimensioni diverse usando gli algoritmi best-fit, worst-fit, first-fit, che se ci pensate è essenzialmente lo stesso processo per questo problema. Il tema generale era senza conoscere tutte le richieste prima del tempo, non è possibile esaminare tutti gli orientamenti possibili e trovare il "minimo" scarto. Puoi avvicinarti usando qualcosa come best-fit ma poi un diverso insieme di ordini potrebbe renderlo peggio del primo e così via, dato che non puoi garantire di guardare avanti abbastanza da ottimizzare tutto in un sistema realistico.

Solo fare alcune situazioni veloci con pochi stick e pochi ordini e variando l'ordine in cui arrivano gli ordini dovrebbe spiegare perché qualsiasi algoritmo che hai potrebbe non restituire sempre la soluzione 'più corretta'.

Stai chiedendo di una classe di problemi equivalenti, ad esempio l'algoritmo di bin-packing (che è NP difficile vedere link ). Non è possibile garantire una soluzione perfetta per qualsiasi numero di clienti e si blocca in un lasso di tempo (ragionevole) lineare. Ciò che puoi fare è usare l'euristica per ottenere una soluzione "best effort".

Dai un'occhiata al packing dei contenitori e pensa a come mappare il tuo problema alle solite soluzioni best effort è probabilmente l'approccio migliore.