aiuto cerco algoritmo

ola a tutti
ho bisogno di un piccolo aiuto
vorrei sapere se esiste, o qualcuno di voi skillatissimi sviluppatori riesce a farlo (pago in natura), un algoritmo che se gli do come input una lista di numeri, più o meno lunga, e un numero che deve essere il risultato, mi cerca nella lista e restituisce gli n numeri che sommati danno il numero che ho inserito come risultato. (se possibile anche con approssimazione di +/- 1 sul risultato.

non so se mi sono spiegato bene ma per esempio

inserisco lista numeri
3
7
2
9
11
5

e il risultato 20

e l'algoritmo mi restituisce 9 + 11 e 7+2+11 (in quanto combinazioni di numeri della lista data che se sommati mi danno il numero inserito come risultato)

mi affido a voi :bow:

i numeri possono essere ripetuti?
Comunque io prima farei un vettore con dentro tutti i numeri. Quindi proverei esaustivamente tutte le combinazioni, facendo sottrazioni.
Del tipo
int a,*vett,i,ris;
vett0(int*)malloc(100*sizeof(int));
//INSERISCI I NUMERI nel vettore
//inserisci il ris, nel tuo caso 20
quindi per girare dentro al vettore e provare tutte le combinazioni dovresti usare fmod(i,nunelementi). parti da i=0 e fai ogni volta i=i+n. n lo fai crescere da 1 a numelem. Quindi iteri sommandi u numeri in posizione i finchè o trovi i valori o lo superi.
sarebbe
for(n=0;n<numelem;n++)
i=n; num=0;
while(num<ris)
{
i=fmod(i,numelem);
num=num+vettore[i];
if (num=ris) break;
}
num=0;
i=n;
while(num<ris)
{
printf("");
}
Son a lezione, è scritto in maniera confusa ma dovrebbe essere giusta.

Se non puoi ripetere i numeri, a ogni iterazione tieni traccia dei numeri che hai già usato e se si dovesse ripetere salti l'iterazione

Se invece vuoi tutte le combinazioni, tieni traccia della n che le genera.

ehm colpa mia che non ho specificato ma non ne capisco assolutamente un cazzo di codice e programmazione, quindi mi servirebbe il tutto già impacchettato in un programmino pronto da usare :__D

ris==> vettore 2 righe m colonne iterato da vct
FOR(i=0;i<numelem;i++)
{
FOR(N=0;N<numelen;n++)
{
k=i; num=0;
while(num<ris)
{num=num+vett[k]; k=fmod(k+n,numelem); if( ris==num) ris[1][vct]=i ris[2][vct]=n}
}
}
QUINDI giocando con l'algebra mdulare potresti andare a togliere soluzioni identiche, che comunque non dovrebbero esserci

Lol. Te hai chiesto un algoritmo. Volendo potrei anche scriverti il codice ma peenso che sia molto poco efficiente, ti conviene chiedere a ch queste cose le sa fare davvero. Se i numeri son piccoli il mio codice dovrebbe funzionare, se i numeri son grossi son cazzi

Ad esempio così su due piedi, un approccio a albero potrebbe funzionare molto meglio, ordinando i numeri in modo decrescente. Magari mettendo una condizione sulla somma di tutti i numeri in funzione dei numeri che son rimasti.

Questo?
http://stackoverflow.com/questions/4...ch-a-given-sum

Edit: ho verificato lo scriptino python che presentano, fa effettivamente quello che ti serve

Un algoritmo non ricorsivo è cmq più veloce di uno ricorsivo a quel che so io

Stai parlando della variante non decisionale del subset sum. Googla che trovi sicuro qualche implementazione.
Inoltre, forse ho qualche implementazione in giro dai tempi dell'uni, mo ci guardo

edit:
trovato, riporto di seguito. E' programmazione dinamica, potrebbe non essere intuitivo a livello di comprensione

public class SubsetSum {

//Matrice binaria
public static int m[][];

//Matrice delle direzioni
public static String d[][];

//Matrice delle direzioni aggiuntive
public static String w[][];

//Vettori per la stampa
public static int g[];
p3'ublic static int p[];

//Algoritmo Subset Sum
public static void SS (int v[], int b){

int k = b+1;
int lung = v.length;

m = new int[lung][k];
w = new String[lung][k];

for (int i=0; i<k; i++)
m[0][i]=0;

m[0][v[0]]=1;
w[0][v[0]]="u";

for (int i=1; i<lung; i++)
for (int j=0; j<k; j++){
if(j==v[i]){
m[i][j]=1;
if(m[i-1][j] == 1){
w[i][j] = "s";
}
else
w[i][j] = "u";
}
else {
m[i][j]=m[i-1][j];
w[i][j] = "a";


if(j>v[i] && m[i-1][j-v[i]]>=m[i][j]){
m[i][j]=m[i-1][j-v[i]];
w[i][j] = "d";
}

if(j>v[i] && m[i-1][j-v[i]] == m[i-1][j])
w[i][j] = "s";

}
}

//Il codice seguente serve per stampare la matrice binaria e la matrice delle direzioni

/*System.out.print("Matrice binaria M: ");
for(int s=0; s < lung; s++){
System.out.print("\n");
for(int t=0; t<k; t++)
System.out.print(m[s][t]);
}
System.out.print("\n");

System.out.print("Matrice delle direzioni d: ");
for(int s=0; s < lung; s++){
System.out.print("\n");
for(int t=0; t<k; t++)
System.out.print(w[s][t]);
}
System.out.print("\n");*/

}


//Funzione per la stampa del capitale massimo necessario per acquistare un sottoinsieme dei pacchetti presenti sul mercato
public static void PrintCapMax(int v[], int i, int j){

boolean ctrl = false;
for(;j >= 0 && ctrl == false; j--)
if(m[i][j] == 1){
System.out.println("Cifra massima necessaria per acquistare un sottoinsieme dei pacchetti presenti sul mercato: "+j);
ctrl = true;
}
}

//Funzione che indica quali sono tutti i possibili sottoinsiemi di pacchetti acquistabili.
public static void PrintSS (int v[], int i, int j, int cont){


if(i==0 || j==0){
if(m[i][j]==1){
g[cont] = v[i];
p[cont] = i;
cont++;
}

for(int y = cont-1; y >= 0; y--)
System.out.println("Pacchetto "+(p[y]+1)+" di valore "+g[y]);

System.out.println("");

return;
}

if(w[i][j]=="d" || w[i][j]=="u") {

g[cont] = v[i];
p[cont] = i;

PrintSS(v,i-1,j-v[i], cont+1);
}

if(w[i][j]=="a")
PrintSS(v,i-1,j, cont);

if(w[i][j]=="s"){

g[cont] = v[i];
p[cont] = i;

PrintSS(v,i-1,j-v[i], cont+1);

PrintSS(v, i-1, j, cont);
}
}

public static void main(String args[]){

//Inserimento valori da tastiera tramite SavitchIn

int max = 0;

System.out.println("Inserisci il valore del capitale: ");
int k = SavitchIn.readInt();


System.out.println("Inserisci il numero di pacchetti presenti sul mercato: ");
int n = SavitchIn.readInt();

int v[];

v = new int [n];

for(int i=0; i<n; i++){
System.out.println("Inserisci il prezzo del pacchetto: "+(i+1));
v[i]=SavitchIn.readInt();
if(v[i] > max)
max = v[i];
}

if(max > k){
System.out.println("Il capitale inserito è troppo piccolo e non permette l'acquisto di alcun pacchetto.");
return;
}


SS(v,k);
PrintCapMax(v, n-1, k);

System.out.println("\n");

g = new int[n];
p = new int[n];
int cont = 0;

PrintSS(v, n-1, k, cont);
}
}

Quel che interessa a te è la printSS, l'algoritmo in questione faceva anche roba in più.

imho Burner ci sta trollando... :nod:

Quote:

---

Originally Posted by Brcondor

Lol. Te hai chiesto un algoritmo. Volendo potrei anche scriverti il codice ma peenso che sia molto poco efficiente, ti conviene chiedere a ch queste cose le sa fare davvero. Se i numeri son piccoli il mio codice dovrebbe funzionare, se i numeri son grossi son cazzi

---

Non è questione di come scrivere il codice, è l'idea di fondo che è sbagliata. Quella che hai riportato tu è la soluzione naive, con un tempo di calcolo mostruoso.

A titolo di curiosita`, Burner: limitatamente all'ambito in cui voresti utilizzare l'algoritmo, che ordine di grandezza ha il numero di elementi dell'insieme dato in ingresso e con che frequenza accederesti alla funzione?

prima di tutto grazie a tutti per le risposte

poi forse mi sono spiegato male dal titolo del topic, ma non mi serve solo l 'algoritmo, ma qualcosa di già funzionante tipo web app, software eseguibile, foglio di cacolo excel ecc, perchè non ho idea di come far funzionare l'algoritmo da solo :D

per rispondere a Dr.Doomed sto programma mi servirebbe per andare a rintracciare movimenti di soldi :D
in pratica copio tutti i numeri di un estratto conto ad esempio e tra tutti quei numeri cerco quelli che se sommati danno esattamente l'importo che dico io.

Quote:

---

Originally Posted by Burner

per rispondere a Dr.Doomed sto programma mi servirebbe per andare a rintracciare movimenti di soldi :D
in pratica copio tutti i numeri di un estratto conto ad esempio e tra tutti quei numeri cerco quelli che se sommati danno esattamente l'importo che dico io.

---

Ok, grazie.

File zip--> Attachment 9860
Ho compilato il file di Axet, rimuovendo i riferimenti a SavitchIn e sostituendoli con una classe Scanner in lettura sullo standard input.
In teoria, scompatti il tutto, entri nella directory bin e lanci "java ss.SubsetSum < ssconfig.dat": dovrebbe stamparti a schermo la soluzione del quesito iniziale. Oh, accrocchietto fatto in 5 min, non garantisco: sul mio windows 7 con java runtime installate funziona. ;)
Il file di configurazione e` organizzato cosi` da avere nella prima linea la cifra obiettivo, nella seconda il numero di valori (diciamo n) e nelle rimanenti n righe gli n valori.

Premetto che non so se quel codice è a prova di bug, era per un esame che mi era fruttato 30L quindi in teoria non dovrebbe aver problemi.
In pratica boh, mai utilizzato poi in seguito.

Ma quindi burner la tua richiesta è stata esaudita? :nod: