Newsgroup: it.comp.lang.visual-basic
Titolo: Un problema di numeri

Se io i seguenti 5 numeri:
1 10
2 5
3 15
4 20
5 10
totale=60
vorrei poterli dividere in due gruppi la cui somma si avvicini il più
possibile alla metà del totale generale, esempio:
4 20
5 10
totale=30
1 10
2 5
3 15
totale=30
Ovviamente l'algoritmo dovrebbe essere efficiente con un numero superiore di
numeri ed anche quando è impossibile dividere esattamente a metà la somma
totale dei numeri.
Ovvero:
1 40
2 27
3 18
4 1
totale= 86
risultato voluto:
1 40
4 1
totale=41
2 27
3 18
totale=45
Come posso fare?
Grazie :)

Questo che ti propongo è una soluzione di tipo euristico (non è dettto che
il risultato ottenuto sia la soluzione migliore):
Chiamiamo X l'insieme dei numeri dati e A, B i due insiemi che vogliamo
ottenere. 
-Dall'insieme di origine X andrà estratto sempre il max.
-Si inizia l'algoritmo estraendo il max da X e collocandolo
indifferentemente in A o B.
-Ogni altro numero estratto da X andrà collocato nell'insieme (A o B) la
cui somma dei numeri precedentemente inseriti sia la minore.
Ciao Marco
--- 
Remove xxx from E-mail.

...

Esistono diversi approcci per la soluzione di questo problema.
1) calcolo "brute force" di TUTTE le possibili combinazioni di
raggruppamenti
PRO: massima precisione (miglior avvicinamento alla meta' del totale)
CONTRO: elevata complessita' computazionale (ci mette piu' tempo)
2) ricerca "euristica", ossia si ordinano i numeri dal maggiore al minore:
1 40
2 27
3 18
4 1
partendo dal primo si somma fino a trovare un numero abbastanza vicino alla
meta' del totale (es. 40 e' piu' vicino a 43 che non 40+27=67)
Poi si sommano tutti i restanti tra loro (27+18+1 = 46)
PRO: estrema semplicita' implementativa e buona velocita' con molti dati
CONTRO: come si puo' vedere dall'esempio fatto, il risultato non e' ottimale
(anche se puo' migliorare con tanti dati)
3) uso di algoritmi genetici (sono algoritmi che riprendono cio' che avviene
in natura, ossia ad ogni "generazione" di calcoli e relativi risultati il
risultato migliora).
PRO: danno buoni risultati (con costi intermedi tra le due soluzioni
descritte prima)
CONTRO: presuppongono uno studio della teoria degli algoritmi genetici (che
non e' semplicissima).
E' possibile pensare anche ad algoritmi "ibridi", ossia una ricerca
euristica (punto 2) con perfezionamento "brute force" su una parte dei dati
gia' selezionati, che consente di aumentare la bonta' del risultato, ma
limitando i costi in termini computazionali.
La scelta dipende dal compromesso tra velocita' e bonta' del risultato che
vuoi ottenere.
--
Roal Zanazzi
z...@iol.it

 esempio applicando un algoritmo di simulated anneling:
Supponiamo di avere a disposizione 100 numeri disposti in una lista o vettore
Y:(1) fai la somma di tutti i numeri del vettore Y e memorizzala in una
variabile W(2) estrai a caso un numero dal vettore Y utilizzando una funzione
Random (rnd) ed
    inseriscilo in un nuovo vettore X
(3) inizializza una variabile Z ed inserisci il numero estratto
(4) se Z è maggiore di W allora ESCI e STAMPA
(5) estrai a caso un  nuovo numero dal vettore Y ed inseriscilo in un nuovo
vettore X
(6) somma il nuovo numero a Z, cioè Z = Z + numero
(7) vai a (4)
Ripeti questo ciclo per un numero di iterazioni a tua scelta, a seconda del
tempo che vuoi fargli impiegare e confronta ad ogni iterazione se il valore di Z
è più vicino alla metà di W della migliore soluzione trovata.
esempio:
Zmax = 0
for i = 0 to niterazioni
    Esegui Ciclo precedente
    if (Z - W)<(Zmax-W) then  Zmax = Z
next
Ciao Leonardo

>
1) calcoli la meta della somma dei numeri
2) li ordini per dimensioni
3) Dai al primo insieme(i1) il valore del numero + alto
4) Dai al secondo insieme(i2) il valore del secondo numero + alto
ripeti i punti 5 e 6 finchè i numeri da sommare sono finiti
5) Somma a i1 il numero + basso rimasto
6) sooma a i2 il numero + basso rimasto (il 2 + basso visto che il primo è
stato sommato a i1)
es:                    | diventa ordinandoli: | nel loop:
1)54                 | 1)78                           |i1=78+4
2)78                 | 2)56                           |i2=56+9
3)56                 | 3)54                           |i1=78+4+18
4)4                   | 4)18                           |i2=56+9+54
5)9                   | 5)9                              |
6)18                 | 6)4                             |i1=100
                         | i1=78                         |i2=119
                         |i2=56                          |
Premettendo che non è il metodo più esatto ma sicuramente il + veloce , e
che per renderlo + esatto basterebbero un paio di accorgimenti dopo il
loop*,spero che ti sia di aiuto.
*tipo:
x=i1 se i1>i2 ; x=i2 se i2>i1
y=meta della somma di tutti i numeri
somma l'ultimo numero (il minore) al penultimo,al terz'ultimo, e cosi via,
finchè il risultato rimane minore di x-y, poi sottraia  x il valore di y, e
aggiungi x all'altro insieme....
Forse un pò macchinoso ma penso pur sempre veloce...

Ho adottato il sistema euristico, mi sembra molto semplice veloce e
abbastanza efficiente.
Grazie a tutti :)


Se i numeri non sono tantissimi potresti provare con la forza bruta:
provi tutti i casi e vedi qual'è il migliore.
In pratica si tratta di creare tutti i gruppi possibili, formati da
metà dei numeri a disposizione: il rimanente determina automaticamente
l'altro gruppo.
Se ad esempio avessi 20 numeri il numero di casi da provare sarebbe
pari alle combinazioni di 20 elementi a 10 a 10, che dovrebbero essere
184756, se non ho sbagliato.
Il calcolo è il seguente:
(20*19*18*17*.....*12*11)/(10*9*8*7*...*2*1)
Dovrebbe anche essere facile pilotare la scelta dei gruppi in modo da
eliminare in partenza i casi che sicuramente non andrebbero bene.
Potresti partire ordinando i numeri e scegliendoli, in linea di
principio, uno si e uno no.
Ciao
--------------------------------------------------------------------
Fulvio Senore
Eliminate "zz" dall'indirizzo e-mail per scrivermi (spammers...)
Remove "zz" from e-mail address to write me (spammers...)
--------------------------------------------------------------------

...


La soluzione che ho proposto è di tipo euristico. Naturalmente, come tu
dici, miglioramenti si possono ottenere pre-ordinando il vettore con un
algoritmo:  la complessità computazionale del Quick-sort è O(n*lg(n)).  
Ciao Marco.
-- 
Remove xxx from E-mail.

Il mio era un apprezzamento nel senso che non ho trovato un caso in cui il
tuo metodo non funzioni bene. Tu ne hai uno da espormi?
Ciao
Antonio Donatiello
Marco Rodriquez ha scritto nel messaggio
<01be2ce7$78ccae60$1e26d8d4@rodry>...


tuo metodo non funzioni bene. Tu ne hai uno da espormi?
Un caso in cui il metodo non funziona è il seguente: [13 12 7 7 7 7 4]
somma=57
si ottengono i due insiemi :[13 7 7] somma=27 e [12 7 7 4] somma=30
Un risultato migliore è ottenuto con i seguenti ragruppamenti:
[13 12 4] somma=29 e [7 7 7 7] somma=28
