Qual è un buon algoritmo di smistamento per mettere elementi in contenitori e mantenendo i contenitori il più possibile il più possibile?

Question

Quindi in realtà lo userò per fare qualche generazione di layout della forma dinamica in Extjs4, ma penso di poter semplificare il problema verso il basso per facilitare la discussione senza perdere nulla:

Diciamo che ho una lista di numeri interi che voglio collocare all'interno di due contenitori. Quando ho finito, voglio che entrambi i contenitori siano "il più possibile", che in questo caso significa che le somme dei numeri interi all'interno di ogni contenitore sono altrettanto vicine l'una all'altra come possiamo prenderli. In questo scenario non importa quanti interi finiscono in ogni contenitore, semplicemente che le loro somme sono vicine.

Ecco un esempio di un possibile ingresso e un'uscita desiderabile:

Integers: [1,7,13,3,6,8]
Container A: [13,6] (sum 19) 
Container B: [1,7,3,8] (sum 19)

.

Un approccio ingenuo potrebbe essere quello di iterare sopra l'elenco intero una volta, e inserire il numero intero nel contenitore che attualmente ha la somma più piccola:

Integers: [1,7,13,3,6,8]
Container A: [1,13,8] (sum 22)
Container B: [7,3,6] (sum 16)

.

Quale algoritmo / approccio vorresti suggerire di affrontare questo problema? Immagino che ci siano alcuni potenziali. Se trovi più facile pensare nei campioni di codice, implementerò il prodotto finale in JavaScript.

Grazie!

---

.

Modifica

Mi piacciono i due approcci presentati finora (grazie CHEINGEN e SUMUDU FERNANDO), entrambi dei quali danno buoni metodi per ottenere rapidamente qualcosa vicino a (o esattamente) la risposta ideale. Per un piccolo insieme di numeri interi immagino che potresti semplicemente forzare un calcolo e dire definitivamente che la risposta particolare è la migliore (o legata al meglio). Qualche suggerimento per fare qualcosa del genere? In altre parole, un approccio che garantisce una risposta ideale al costo di potenzialmente lento (o completamente irrealibile per gruppi di problemi di grandi dimensioni).

Answer 1

.
1. Calcola la somma di tutti gli elementi.
2. Calcola metà della somma, s.
3. Applica il problema di zaino al numero rendendo la somma di destinazione s.
4. Metti la soluzione in un contenitore e gli elementi rimanenti nell'altro contenitore.