aiuto cerco algoritmo

[Burner]

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:

[Brcondor]

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.

[Brcondor]

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

[Brcondor]

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

[Burner]

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

[Brcondor]

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

[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

[Brcondor]

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.

[Dr.Doomed]

Questo?
http://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

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

[Brcondor]

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

[Axet]

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);
}
}

[Axet]

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

[Verci]

imho Burner ci sta trollando... :nod:

[Axet]

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.

[Dr.Doomed]

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?

[Burner]

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.

[Dr.Doomed]

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--> 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.

[Axet]

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.

[Axet]

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