riempire contenitori con blocchi di dimensioni diverse per avere contenitori di dimensioni "simili" [chiuso]

Naviga le tue risposte
2

Ho una lista ordinata di blocchi L che voglio mettere in 4 contenitori C , i contenitori hanno un limite di dimensione S . Voglio avere altezza contenitori simili, per analogia intendo dire che la variazione della dimensione dovrebbe essere la più piccola possibile.

es: 

S = 4
L = [1, 1, 3, 1, 2, 1, 2]

dovrebbe risultare in: 

C = [[1, 1], [3], [1, 2], [1, 2]]

nota: è sempre possibile inserire tutti i blocchi all'interno dei 4 contenitori e non posso modificare l'ordine dei blocchi

c'è un modo per farlo in modo efficiente? Non sono riuscito a trovare nomi di algoritmi su questo argomento ma non sapevo davvero come cercarlo

    
posta Mathieu 13.12.2013 - 11:54
fonte

1 risposta

4

Questa è una generalizzazione del problema dello zaino (seleziona gli elementi di un set in modo che la loro somma sia esattamente n ). Si desidera selezionare quattro sottoinsiemi di elementi in modo che la somma di ogni sottoinsieme sia n (dove n è 1/4 della somma di tutti i blocchi), quindi è una variante più difficile del problema standard

Sfortunatamente, il problema dello zaino è noto per essere NP-completo, ovvero praticamente irrisolvibile per il grande n . Tuttavia, esiste una ricca letteratura sulle soluzioni approssimative , che è ciò che desideri.

    
risposta data 13.12.2013 - 11:58
fonte

Leggi altre domande sui tag

Uso di normali classi Java nelle app Web Java Voglio vendere una semplice calcolatrice. Qual è il modo più semplice per implementare le chiavi di registrazione?