Come dividere un elenco di elementi in partizioni uguali in base al peso dell'articolo?

Question

Ho un elenco di elementi che è un po 'come questo:

[ 
    ["orange", 9], 
    ["watermelon", 3], 
    ["grapefruit", 6], 
    ["peach", 8], 
    ["durian", 2], 
    ["apricot", 6] 
] 

Vorrei dividere questo elenco in ... dire due gruppi in modo che la somma dei pesi delle voci in ogni gruppo sono i uguale possibile, vale a dire:

List 1: 
    orange: 9 
    durian: 2 
    apricot: 6 
    TOTAL: 17 

List 2: 
    watermelon: 3 
    grapefruit: 6 
    peach: 8 
    TOTAL: 17 

Attualmente mi sto risolvere questo attraversando l'elenco ordinato in modo zigzag'esque. Assegnare gli oggetti con più peso nel primo passaggio a ciascun gruppo, assecondando gli oggetti con meno peso sul secondo passaggio e così via.

Questo funziona bene, ma ha difetti. Sto pensando che un secondo passaggio sui gruppi in cui scambio articoli tra di loro porterebbe a gruppi più equamente distribuiti, ma il codice in questione potrebbe diventare troppo complicato.

Qualcuno sa di un modo più efficiente o intelligente per farlo?

Grazie!

Answer 1

Questa è la versione di ottimizzazione di partition problem, che è NP-completa, anche se, secondo questo articolo, "ci sono euristiche che risolvono il problema in molti casi, in modo ottimale o approssimativo."

La sezione methods di questo articolo contiene una serie di modi per fare soluzioni approssimative o pseudo-polinomiali. In particolare, se si può vivere con una risposta approssimativa, si potrebbe provare l'approccio greedy:

Un approccio al problema, imitando il modo in cui i bambini scelgono squadre per un gioco, è l'algoritmo greedy, che passa attraverso i numeri in ordine decrescente, assegnando ognuno di essi a qualsiasi sottoinsieme ha la somma minore.

Il tempo di esecuzione di questo approccio è O(n^2) ed è garantito per farti arrivare entro un fattore di 4/3 della soluzione esatta.

Se è necessario disporre di una soluzione esatta e il set di dati è abbastanza piccolo, è sempre possibile adottare un approccio a forza bruta per generare ogni possibilità (questo è esponenziale, O(2^n)). A seconda delle esigenze di prestazioni, questo potrebbe essere sufficiente.

Answer 2

È possibile sommare tutti i pesi, dividere per il numero di gruppi, ottenere un peso target e quindi scorrere tra gli oggetti in ordine di peso decrescente lanciarli nello stesso gruppo se si adattano al peso target o al di sotto di esso. e nell'altro gruppo se non lo fanno.

Probabilmente c'è qualche drs di matematica là fuori che può trovare una dimostrazione formale del modo migliore per farlo, ma questo è stato il mio pensiero fuori di testa.

Answer 3

Non funzionerà. Ad esempio, S = {5, 5, 4, 3, 3}.