Newsgroup: it.scienza.informatica
Titolo: Java e programmazione in generale

Salve recentemente mi sono trovato davanti a un problema che non so
risolvere, premetto che sono un novellino in java, il problema e' il
seguente: dato un array di interi come posso calcolare tutte le possibili
combinazioni di numeri che sommati mi diano un certo numero x?
Vi ringrazio anticipatamente

 ha riferito agli onorevoli
membri di questo NG:

Ti posto la mia soluzione (forse computazionalmente si
potrebbe fare di meglio) in pseudo linguaggio :
array=(1,4,5,2,3,12,34);
x=8;
num_elementi=count(array);
 //contiene la lunghezza 	 dell'array
for (i=0;i<=num_element-1;i++) {
	for (j=i+1;j<=num_elementi-1;j++) {
                 if (array(i)+array(j)==x) {
	   print 'array(i) e array(j) danno come somma
x_-gli indici sono i e j' ;
	} //fine if
 	} //fine for interno
}//fine for esterno
Spero sia quello che cercavi.
It's just a joint...
Set me Free!!

Io avevo pensato a questo:
for (int z=valori.length-1; z>=1; z--)
         {
         for (int j = 0; j<z; j++)
   {
                                if (valori[j]+valori[z]==costante)
    {
     System.out.println("X = "+lettere[j]+" + "+lettere[z]);
                               s="X = "+lettere[j]+" + "+lettere[z];
          v.addElement(s);
                                }
                        }
 }
 cmq il mio problema e' sapere tutte le cobinazioni possibili tramite una
"formula universale", a coppie, triple ecc. cmq grazie lo stesso

Ordina l'array
Per i=1 fino a N
      Per k>=i fino a k=N
           componi la coppia (A[i],A[i+k]) e calcola la somma
                Se la somma soddisfa il tuo criterio segna da qualche parte
la coppia
Se la combinazione è di k numeri su n, allora dovresti agiungere un ciclo
per ogni k>2 e selezionare tutti gli elementi..........


Ma combinazioni sono coppie? o sono generiche tuple?
se sono coppie si fa in tempo lineare
in A c'e' l'array lungo N dove ci sono i numeri
X e` la somma che devono fare
metto A su un hash
scorro A prelevando gli elementi A[i]
cerco X-A[i] sull'hash. Se c'e' produco in output la coppia <A[i], X-A[i]>.
viene lineare, di meno direi che non si puo` fare.
*Se* invece per combinazioni si intendono combinazioni di k numeri
allora e` ovviamente riconducibile al problema dello zaino.
Se vuoi la soluzione esatta non c'e' che da provarle tutte.
Magari riordina l'array cosi` eviti un po` di lavoro inutile.

Preferirei usare un albero binario da esplorare con una procedura ricorsiva,
in questo caso potresti risparmiare parecchio tempo scartando tutti quei
nodi con valore già superiore ad X e quelli dai quali non si potrebbe
superare X nemmeno aggiungendo tutti i restanti elementi dell'array.

 wrote in message
Mdth8.12345$uN5.3...@twister1.libero.it...

ti consiglio di andarti a cercare qualche algoritmo di Backtracking che
risolva
questo problema che ad occhio mi sembra non polinomiale...


Un albero di dimensione esponenziale direi che non va bene  :-).
Giorgio

In questo caso, come ho detto nel mio post, è possibile introdurre alcuni
bound per evitare di esplorare tutti i nodi; posso fare questa affermazione
perchè mi è capitato di risolvere un altro problema riconducibile a quello
dello zaino e utilizzando questa tecnica con dati di ingresso casuali ho
osservato il raggiungimento della soluzione esplorando una quantità di nodi
di molto inferiore a 2^N (tipo N=50, nodi esplorati=450 mediamente).
Ovviamente nel caso peggiore la soluzione si raggiunge esplorando 2^N nodi
come dici tu.