Dato un valore, vedere se è ricavabile sommando gli elementi di un array

[crissstian96]

Ho bisogno di una cosa un po' strana a cui non riesco a venirne fuori, vorrei solo sapere come farlo a livello logico, che poi per la codifica ci penso io.
Io ho un valore e un array, ad esempio
int x = 8;
int v[] = {4, 7, 3, 1};

vorrei sapere, tramite il codice, se è possibile ottenere il valore x sommando i numeri nel vettore v.
Nell'esempio, questo ipotetico metodo, dovrebbe ritornare vero poiché 4 + 3 + 1 = 8
Ma se invece x=9; allora dovrebbe ritornare falso perché non c'è nessuna combinazione la cui somma dà 9.

A livello di analisi, ho creato un metodo ricorsivo che, però, va in loop ricevendo un errore di stack overflow, il metodo è il seguente:

private static boolean existValueC(int x) {
		int k;
		for(k=x; k>0; k--){
			if(k!=(x-k)){
				if(map.containsValue(k)&&map.containsValue(x-k))
					return true;
			}
			else if(containsTwoTimes(k))
					return true;
					
		}
		for(k=x; k>0; k--)
		      if(existValueC(x)&&map.containsValue(x-k))
			  return true;
		for(k=x; k>0; k--)
		       if(map.containsValue(k)&&existValueC(x-k))
				return true;
		for(k=x; k>0; k--)
			if(existValueC(k)&&existValueC(x-k))
				return true;
		return false;
	}
	private static boolean containsTwoTimes(int k) {
		map.put(getKeyByValue(map, k), 0);
		return map.containsValue(k);
	}
	public static <T, E> T getKeyByValue(Map<T, E> map, E value) {
	    for (Entry<T, E> entry : map.entrySet()) {
	        if (value.equals(entry.getValue())) {
	            return entry.getKey();
	        }
	    }
	    return null;
	}

Il fatto che sia una map o un array è irrilevante.
Potete aiutarmi?

[andbin]

Io ho un valore e un array, ad esempio
int x = 8;
int v[] = {4, 7, 3, 1};

vorrei sapere, tramite il codice, se è possibile ottenere il valore x sommando i numeri nel vettore v.
Nell'esempio, questo ipotetico metodo, dovrebbe ritornare vero poiché 4 + 3 + 1 = 8

Fai tutte le combinazioni possibili prendendo ciascun valore nell'array 0 o 1 volta.
Detto con il tuo esempio: quanti numeri ci sono in v? 4 E quante somme "combinate" puoi fare? 2^4 = 16.

4 7 3 1   somma
---------------
0 0 0 0   0
0 0 0 1   1
0 0 1 0   3
0 0 1 1   4
0 1 0 0   7
.....

[Patrick Jane]

Forse la sparo grossa, magari però puo' essere un idea.

Hai il tuo array, potresti quindi ordinarlo (utilizzando ad esempio <i>sort()</i> di Arrays) e poi posizionarti a metà di esso. Inizierai quindi a scorrerlo da un lato e dall'altro. La semplificazione in questo caso è data dal fatto che il numero x è dato dalla somma di un numero che è in una metà con un altro che è nell'altra. Un altro vantaggio è interrompere il ciclo quando vai oltre alla somma. Nel tuo caso se hai {1,3,4,5,7,9} la metà è a lunghezza/2-1 (valore 4).
Ti conviene secondo me iniziare con un indice su 0 e l'altro su (lunghezza-1), in quanto ti permette di uscire da uno dei cicli. In pratica fai già 1+9=10, quindi decremento il secondo indice puntato sul 7. Ricomincio quindi a contarli facendo 7+1=8 e proseguo così...

Questo è per darti un idea.

[Andrea1979]

Oltre ai suggerimenti di andbin e Patrick Jane, ti vorrei indirizzare verso una lettura "obbligatoria" (dal punto di vista puramente culturale), dopo che ti ci sarai scervellato un po': è un problema noto come "knapsack problem" o "problema dello zaino".

[crissstian96]

Fai tutte le combinazioni possibili prendendo ciascun valore nell'array 0 o 1 volta.
Detto con il tuo esempio: quanti numeri ci sono in v? 4 E quante somme "combinate" puoi fare? 2^4 = 16.

4 7 3 1   somma
---------------
0 0 0 0   0
0 0 0 1   1
0 0 1 0   3
0 0 1 1   4
0 1 0 0   7
.....

Già avevo pensato ad una soluzione simile, dato che è maggiormente ottimizzato poiché esegue 2^x iterazioni, mentre il mio esempio è qualcosa come x*(x!), dunque il risparmio è notevole.
Il problema è che impossibile da implementare, cioè non saprei proprio da dove iniziare.
Si potrebbe fare un vettore di boolean in cui ogni esponente di due cambi il valore di se stesso e del suo vicino, ci ragionerò su.

[crissstian96]

Forse la sparo grossa, magari però puo' essere un idea.

Hai il tuo array, potresti quindi ordinarlo (utilizzando ad esempio <i>sort()</i> di Arrays) e poi posizionarti a metà di esso. Inizierai quindi a scorrerlo da un lato e dall'altro. La semplificazione in questo caso è data dal fatto che il numero x è dato dalla somma di un numero che è in una metà con un altro che è nell'altra. Un altro vantaggio è interrompere il ciclo quando vai oltre alla somma. Nel tuo caso se hai {1,3,4,5,7,9} la metà è a lunghezza/2-1 (valore 4).
Ti conviene secondo me iniziare con un indice su 0 e l'altro su (lunghezza-1), in quanto ti permette di uscire da uno dei cicli. In pratica fai già 1+9=10, quindi decremento il secondo indice puntato sul 7. Ricomincio quindi a contarli facendo 7+1=8 e proseguo così...

Questo è per darti un idea.

Buon ragionamento, però funziona solo con due numeri, e questo il mio algoritmo già lo fa.
Il problema è quando il numero è ottenibile sommando più di 2 numeri, e qua esce fuori un casino.
Grazie lo stesso.

Oltre ai suggerimenti di andbin e Patrick Jane, ti vorrei indirizzare verso una lettura "obbligatoria" (dal punto di vista puramente culturale), dopo che ti ci sarai scervellato un po': è un problema noto come "knapsack problem" o "problema dello zaino".

Questa risposta mi ha migliorato la giornata, almeno so di non essere stupido io, perché mi stavo preoccupando.
Avendo una formula matematica sarà sicuramente più semplice, appena codifico qualcosa di funzionante lo posto così semmai dovesse servire a qualcun altro potrà trovarlo.
Grazie mille a tutti e tre.

[crissstian96]

Ecco il codice:

private static boolean ricavabile(int[] v, int x) {
		boolean b[] = new boolean[v.length];
		int i, exp, acc;
		for(i=0; i<b.length; i++)
			b[i] = false;
		i=1;
		exp = (int) Math.pow(2, v.length);
		while(i<=exp){
			acc=0;
			for(int j=0; j<v.length; j++)
				if(b[j]) acc+=v[j];
			if(acc==x)
				return true;


			for(int j=0; j<v.length; j++)
				if(i%(int) Math.pow(2, j)==0)
					b[j] = !b[j];
			i++;
		}
		return false;
	}

Se avete suggerimenti per migliorare le prestazioni dite pure.
Avevo pensato di ordinare l'array e poi, in caso acc>x ritornare falso, ma per piccoli array il tempo utilizzato per ordinarlo è superiore al tempo risparmiato.