Che cos'è un algoritmo per dividere equamente un gruppo di elementi in 3 gruppi separati?

Ho questo problema nel mio libro di testo: Dato un gruppo di n elementi, ciascuno con un valore distinto V (i), qual è il modo migliore per dividere gli elementi in 3 gruppi in modo che il gruppo con il valore più alto sia minimizzato? Dai il valore di questo gruppo più grande.Che cos'è un algoritmo per dividere equamente un gruppo di elementi in 3 gruppi separati?

So come eseguire la variante a 2 pile di questo problema: richiede solo l'esecuzione indietro dell'algoritmo dello zaino sul problema. Tuttavia, sono abbastanza perplesso su come risolvere questo problema. Qualcuno potrebbe darmi qualche suggerimento?

Risposta: Più o meno la stessa cosa come il 0-1 zaino, anche se 2D

fonte

2012-01-06 Richie Li

Da quando è venuto fuori e scomparso, ecco un esempio di avido fallimento {100, 51, 49, 40, 30, 20, 10}. La risposta ottimale è una divisione perfetta, l'applicazione avidamente più grande elemento non assegnato al gruppo più piccolo non lo è. – ccoakley

Ho lo stesso libro di testo. Brian Dean me lo ha dato;) – joshim5

Duro problema compiti a casa. Questa è essenzialmente la versione di ottimizzazione del problema con 3 partizioni.

http://en.wikipedia.org/wiki/3-partition_problem

è strettamente legato a bin packing, partizione e sottoinsieme-sum (e, come avrete notato, lo zaino). Tuttavia, sembra essere fortemente NP-Completo, il che lo rende più difficile dei suoi cugini. Ad ogni modo, suggerisco di iniziare guardando le soluzioni di programmazione dinamiche ai problemi correlati (vorrei iniziare con la partizione, ma trovare una spiegazione non-wikipedia della soluzione DP).

Aggiornamento: Mi scuso. Ti ho ingannato. Il problema con 3 partizioni divide l'input in set di 3, non di 3 set. Il resto di ciò che ho detto si applica ancora, ma con la rinnovata speranza che la tua variante non sia fortemente np-completa.

fonte

2012-01-06 18:07:59 ccoakley

Ho aggiunto alcune informazioni al problema. –

@RichieLi Domanda onesta: quanti dettagli vuoi che non rovinino il problema? cioè la relazione di ricorrenza desiderata troppo (non che ce l'ho, dovrei lavorarci io stesso)? – ccoakley

Huh, proverò a risolverlo da solo. È previsto la sera, quindi tornerò da te se avessi bisogno di più aiuto. –

Non conosco matematicamente "The Best", ma un approccio ovvio sarebbe creare una popolazione di gruppi inizialmente con un elemento in ciascun gruppo. Quindi, finché hai più gruppi del numero desiderato di gruppi finali, estrai i due gruppi con i valori più bassi e combinali in un nuovo gruppo che aggiungi nuovamente alla raccolta. Questo è simile a come sono costruiti gli alberi di compressione di Huffman.

Esempio:

1 3 7 9 10 
becomes 
4(1+3) 7 9 10 
becomes 
9 10 11(1+3+7)

fonte

2012-01-06 18:12:51

Non abbiamo ancora imparato questo, quindi non penso che dovrei usare questo su questo problema. –

Picking nits: l'approccio goloso è ottimale nel caso huffman (per la codifica a lunghezza variabile di alfabeti fissi). Funziona ragionevolmente per la partizione solo se i numeri del problema sono distribuiti correttamente (dove non posso essere più preciso della parola "benissimo"). Dato che la domanda è stata etichettata come "programmazione dinamica", direi che lo scopo del compito non era quello di usare una tecnica avida. – ccoakley

Sia f [i] [j] [k] indica se è possibile avere valore j nel primo set e valore k nel secondo set, con il prima i articoli.

Quindi abbiamo f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]].

e inizialmente abbiamo f[0][0][0] = True.

per ogni f[i][j][k] = True, aggiornare la risposta dipende da come si definisce piuttosto.

fonte

2012-01-08 04:02:21 Topro

Ma l'elemento ith potrebbe alternativamente entrare nel terzo set, quindi penso che dovrebbe essere "f [i] [j] [k] = f [i-1] [jv [i]] [k] o f [i -1] [j] [kv [i]] o f [i-1] [j] [k] '. –

Inoltre, solo per scriverlo, quando si considera la soluzione per alcuni i, j, k dove f [i] [j] [k] = True, si calcola il peso del terzo set usando s [i] - j - k, dove s [i] è la somma dei pesi dei primi elementi i (precalcolata in tempo lineare all'inizio). –

@j_random_hacker sì, hai ragione. errore mio – Topro

Che cos'è un algoritmo per dividere equamente un gruppo di elementi in 3 gruppi separati?

risposta

Problemi correlati