[C] Vettore: trovare il massimo numero di Sottoinsiemi
Dato l'insieme S contenente N numeri generati a caso fra 1 e 1000, determinare il massimo k.
Ovvero: si vuole partizionare l'insieme S in K sottoinsiemi, in modo tale che la somma di tutti gli elementi che appartengono ai sottoinsiemi sia uguale. Bisogna trovare il K massimo.
N.B. Il problema ha sempre soluzione(K =1 )
Ad esempio : se S ={3, 5, 10, 7, 5 }, K risulterà uguale a 3 e i sottoinsiemi :
P1 = { 3,7 };
p2 = {5,5};
p3 = {10};
Io stavo pensando di crearmi un sottovettore e fare la somma e poi compararlo a un altro, e se la somma è uguale incrementare il numero dei sottovettori.
Come devo fare secondo voi ?
Grazie mille
Ovvero: si vuole partizionare l'insieme S in K sottoinsiemi, in modo tale che la somma di tutti gli elementi che appartengono ai sottoinsiemi sia uguale. Bisogna trovare il K massimo.
N.B. Il problema ha sempre soluzione(K =1 )
Ad esempio : se S ={3, 5, 10, 7, 5 }, K risulterà uguale a 3 e i sottoinsiemi :
P1 = { 3,7 };
p2 = {5,5};
p3 = {10};
Io stavo pensando di crearmi un sottovettore e fare la somma e poi compararlo a un altro, e se la somma è uguale incrementare il numero dei sottovettori.
Come devo fare secondo voi ?
Grazie mille
Risposte
Una prima osservazione che posso fare è che la somma di ogni sottoinsieme deve essere uguale ad un divisore della somma di tutti gli \(N\) numeri. In particolare devo avere \( sum(S) = K \times sum( P ) \) ( \( P \) è uno qualsiasi dei sottoinsiemi ). È poi abbastanza semplice vedere come i divisori che puoi usare debbano essere maggiori del maggiore tra i numeri generati.
Un algoritmo naïve per farlo consiste nel prendere in considerazione tutti gli elementi separatamente, quindi tutte le coppie, le triplette.. A questo punto consideri un divisore dopo l'altro e prendi il più piccolo divisore per cui esiste una partizione dell'insieme. Questo è incredibilmente inefficiente e in pratica l'algoritmo peggiore che puoi usare (insieme ad altre versioni più o meno equivalenti). Per un algoritmo migliore ho bisogno di pensarci un po'..
Un algoritmo naïve per farlo consiste nel prendere in considerazione tutti gli elementi separatamente, quindi tutte le coppie, le triplette.. A questo punto consideri un divisore dopo l'altro e prendi il più piccolo divisore per cui esiste una partizione dell'insieme. Questo è incredibilmente inefficiente e in pratica l'algoritmo peggiore che puoi usare (insieme ad altre versioni più o meno equivalenti). Per un algoritmo migliore ho bisogno di pensarci un po'..
io invece volevo valutare le somme di tutti i possibili sottoarray. Inizializzo il numero dei subarray a 1. Mi creo una variabile per contare il numero di subarray.
Ogni volta che trova un sottoarray la cui somma dei valori è uguale a un altro sottoarray aggiorno il numero di sottoarray. è troppo semplice questa soluzione???
Ogni volta che trova un sottoarray la cui somma dei valori è uguale a un altro sottoarray aggiorno il numero di sottoarray. è troppo semplice questa soluzione???
Le due soluzioni sono abbastanza equivalenti ed entrambe incredibilmente inefficienti. Il numero di sottoarray è infatti uguale a \(2^N\)...
S=somma
N=numero di elementi nell'array iniziale
K=numero di sottoinsiemi
e' ovvio che \(S|N\) e che per i valori di \(S\) che permettono una partizione si avranno in totale \(\displaystyle K=\frac{N}{S}\) sottoinsiemi.
Quindi suggerirei per prima cosa di testera la primalita' di \(N\) con Miller-Rabin, se il numero risulta primo allora abbiamo gia' finito e \(K=1\).
Se invece non e' primo lo fattorizziamo (sfortunatamente questa e' un'operazione inefficente), tra l'altro con Miller-Rabin implementato manualmente si puo' giungere ad un divisore non banale alla svelta, e ci salviamo da qualche parte la lista \(D\) di tutti i suoi divisori (anche non primi), questi divisori sono i nostri candidati per \(S\).
Partendo da \(D_1\) controlliamo che nessun numero nell'array iniziale sia maggiore di \(D_1\), se ne troviamo anche uno solo allora passiamo al prossimo elemento di \(D\)
Se nessun elemento dell'array e' maggiore dell'elemento di \(D\) che stiamo considerando allora proviamo a partizionare l'array in sottoinsieme con gli elementi che sommano a \(D\) (devo pensare ancora esattamente come fare), il primo \(D\) che permette una partizione e' anche quello che massimizza \(K\).
Ok, se qualcuno mi da una mano a pensare come testare per la partizionabilita' in sottoinsiemi che sommano ad un numero dato questa versione mi pare di gran lunga piu' efficente di semplicemente testarli tutti
N=numero di elementi nell'array iniziale
K=numero di sottoinsiemi
e' ovvio che \(S|N\) e che per i valori di \(S\) che permettono una partizione si avranno in totale \(\displaystyle K=\frac{N}{S}\) sottoinsiemi.
Quindi suggerirei per prima cosa di testera la primalita' di \(N\) con Miller-Rabin, se il numero risulta primo allora abbiamo gia' finito e \(K=1\).
Se invece non e' primo lo fattorizziamo (sfortunatamente questa e' un'operazione inefficente), tra l'altro con Miller-Rabin implementato manualmente si puo' giungere ad un divisore non banale alla svelta, e ci salviamo da qualche parte la lista \(D\) di tutti i suoi divisori (anche non primi), questi divisori sono i nostri candidati per \(S\).
Partendo da \(D_1\) controlliamo che nessun numero nell'array iniziale sia maggiore di \(D_1\), se ne troviamo anche uno solo allora passiamo al prossimo elemento di \(D\)
Se nessun elemento dell'array e' maggiore dell'elemento di \(D\) che stiamo considerando allora proviamo a partizionare l'array in sottoinsieme con gli elementi che sommano a \(D\) (devo pensare ancora esattamente come fare), il primo \(D\) che permette una partizione e' anche quello che massimizza \(K\).
Ok, se qualcuno mi da una mano a pensare come testare per la partizionabilita' in sottoinsiemi che sommano ad un numero dato questa versione mi pare di gran lunga piu' efficente di semplicemente testarli tutti
Siete compagni di corso?
"apatriarca":
Siete compagni di corso?
uhm, non ho idea chi sia novella88, ma contando che io vivo in Cina ne dubito fortemente
perche'?
"novella88":
Dato l'insieme S contenente N numeri generati a caso fra 1 e 1000, determinare il massimo k.
Ovvero: si vuole partizionare l'insieme S in K sottoinsiemi, in modo tale che la somma di tutti gli elementi che appartengono ai sottoinsiemi sia uguale. Bisogna trovare il K massimo.
sembra un incrocio tra balanced partition problem e subset-sum problem.
"ascheriit":
[quote="apatriarca"]Siete compagni di corso?
uhm, non ho idea chi sia novella88, ma contando che io vivo in Cina ne dubito fortemente
perche'?[/quote]
Perché novella88 ha inserito il problema oggi e mi è sembrato fossi anche tu interessato alla sua soluzione, ma probabilmente ho visto qualcosa di inesistente nella tua ultima frase.
Ah, capito, beh, diciamo che sono interessato come appassionato di informatica (e su projeceuler.net di problemi relativi a partizionamenti vari ed eventuali ce ne sono un bel po'), ma pagherei caro per andare in una scuola dove mi fanno fare compiti come questo 
@ascheriit: hai provato a vedere tra i vari MOOC (su Coursera, Udacity..)? Forse c'è qualcosa che potrebbe interessarti..
@hamming_burst: quindi escludi una soluzione in tempo polinomiale?
@hamming_burst: quindi escludi una soluzione in tempo polinomiale?
E' la prima volta che sento nominare questi corsi ma sembrano davvero interessanti, ora mi informo per bene, thanks 
(non che mi faccia mancare manuali o cose da studiare in ogni caso
)
tornando al discorso iniziale:
Se vogliamo generare candidati per la somma fattorizzando N allora siamo gia' fuori da un algoritmo in tempo polinomiale.
Quindi per restare in tempo polinomiale non possiamo nemmeno calcolare tutte le possibili somme (divisori di N) ma dobbiamo trovare un buon metodo per approssimare/azzeccare/trovare in qualche modo il valore della somma che massimizza K, personalmente dubito fortemente che si possa fare in tempo polinomiale
(non che mi faccia mancare manuali o cose da studiare in ogni caso
)tornando al discorso iniziale:
Se vogliamo generare candidati per la somma fattorizzando N allora siamo gia' fuori da un algoritmo in tempo polinomiale.
Quindi per restare in tempo polinomiale non possiamo nemmeno calcolare tutte le possibili somme (divisori di N) ma dobbiamo trovare un buon metodo per approssimare/azzeccare/trovare in qualche modo il valore della somma che massimizza K, personalmente dubito fortemente che si possa fare in tempo polinomiale
"apatriarca":
@hamming_burst: quindi escludi una soluzione in tempo polinomiale?
eeh ci sto pensando.
Sembra una generalizzazione del balanced problem, chiamato $k-$partition problem (NP-hard).
La differenza sta nel fatto che quello sopra è un problema decisionale, questo del post di ottimizzazione perchè si richiede il massimo $k$. Quindi non sarei dubbioso che si possa trovare un algoritmo in tempo polinomiale.
ADD:
sembra sia un'ulteriore variante del maximum partition problem, ad una prima lettura di quel testo. Essendoci una limitazione sulla grandezza dei singoli elementi [1,1000] forse c'è qualche possibilita di considerare tale problema un'istanza (lo è ma è piuttosto lasca la differenza), ma la cardinalità di S, non mi pare avere limitazione quindi non vedo altre possibilità che affronta il problema con un algoritmo approssimato. Sono congetture le mie, non ho controllato bene non avendo molto tempo ora.
Mi è venuto in mente la seguente idea di soluzione (è da considerarsi come un abbozzo e non ho provato a calcolarne la complessità). Supponiamo di voler verificare che sia possibile risolvere il problema per un certo $K$. Partiamo quindi suddividendo l'array in $K$ sottovettori a caso. Calcoliamo quindi la somma delle differenze (in valore assoluto) tra la somma dei valori del sottoarray e la somma che deve avere questo array se fosse una soluzione. Questo valore è una stima di quanto la soluzione scelta sia lontana da quella finale. A questo punto possiamo fare due cose per diminuire questa stima:
1. Scambiare due elementi di due sottoarray diversi;
2. Spostare un elemento da un sottoarray ad un altro.
Ad ogni azione corrisponde una variazione del peso e possiamo quindi stimare quanto questa azione sia conveniente. Usando a questo punto un algoritmo di ricerca dovremmo riuscire a trovare la soluzione. Con qualche variazione si può probabilmente anche passare da un particolare numero di sottoinsiemi ad un altro. Credo che la complessità sia ancora non-polinomiale, ma forse è utile vederlo in un modo un po' diverso.
1. Scambiare due elementi di due sottoarray diversi;
2. Spostare un elemento da un sottoarray ad un altro.
Ad ogni azione corrisponde una variazione del peso e possiamo quindi stimare quanto questa azione sia conveniente. Usando a questo punto un algoritmo di ricerca dovremmo riuscire a trovare la soluzione. Con qualche variazione si può probabilmente anche passare da un particolare numero di sottoinsiemi ad un altro. Credo che la complessità sia ancora non-polinomiale, ma forse è utile vederlo in un modo un po' diverso.
ehehe nono non siamo compagni di corso 
io faccio ing.informatica e questo è un esercizio abbastanza tosto e devo trovare la soluzione migliore. Purtroppo quando credo di aver trovato la soluzione mi rendo conto che non lo è..
uff
io faccio ing.informatica e questo è un esercizio abbastanza tosto e devo trovare la soluzione migliore. Purtroppo quando credo di aver trovato la soluzione mi rendo conto che non lo è.. uff
"novella88":
ehehe nono non siamo compagni di corso
uff
di che tipo di corso si tratta? così sappiamo subito, per via gratuita, se è un problema solubile.
@ascheriit:[ot]
"ascheriit":
uhm, non ho idea chi sia novella88, ma contando che io vivo in Cina ne dubito fortemente
perche'?
Cina! lavoro o studio? se posso chiedertelo.[/ot]
Algoritmi e programmazione avanzata..
ma voi siete matematici e siete in gamba:-)
ma voi siete matematici e siete in gamba:-)
ora dato un vettore riesco a ottenere la sequenza di n numeri che da la somma più alta, ma non riesco a visualizzare le somme parziali.. come posso fare secondo voi?
vi posto il codice? lo capite il C?
vi posto il codice? lo capite il C?
Immaginavo l'esame fosse quello*. In questo genere di esami va molto di moda la programmazione dinamica.. Ma per il momento la soluzione migliore che mi è venuta in mente usa un più semplice backtracking (soluzione che per il momento tengo per me - non siamo noi che dobbiamo risolvere il problema dopotutto).
Che tipo di soluzione hai in mente? Non mi è chiaro che cosa intendi con " riesco a ottenere la sequenza di $n$ numeri che da la somma più alta". Siccome i numeri sono tutti positivi, si tratta semplicemente di prendere gli $n$ numeri più grandi (supponendo ovviamente che l'$n$ di cui parli nell'ultimo post sia diverso dalla dimensione dell'array - in tal caso è ancora più immediato). In che senso vuoi "visualizzare le somme parziali"? Che cosa intendi con "la soluzione migliore"? Devi in qualche modo dimostrare questa affermazione (in generale è molto difficile)? Viene comunque considerata valida (ma con un voto forse inferiore) anche una soluzione non ottimale? Non ho problemi a comprendere un programma scritto in C, ma preferirei prima ci spiegassi che algoritmo hai in mente.
* sei di Torino? Oppure usano lo stesso nome ovunque?
Che tipo di soluzione hai in mente? Non mi è chiaro che cosa intendi con " riesco a ottenere la sequenza di $n$ numeri che da la somma più alta". Siccome i numeri sono tutti positivi, si tratta semplicemente di prendere gli $n$ numeri più grandi (supponendo ovviamente che l'$n$ di cui parli nell'ultimo post sia diverso dalla dimensione dell'array - in tal caso è ancora più immediato). In che senso vuoi "visualizzare le somme parziali"? Che cosa intendi con "la soluzione migliore"? Devi in qualche modo dimostrare questa affermazione (in generale è molto difficile)? Viene comunque considerata valida (ma con un voto forse inferiore) anche una soluzione non ottimale? Non ho problemi a comprendere un programma scritto in C, ma preferirei prima ci spiegassi che algoritmo hai in mente.
* sei di Torino? Oppure usano lo stesso nome ovunque?
per somme parziali intendo che, dato un vettore di n numeri, faccio la somma totale e poi prendo i numeri ( a caso a due o due, oppure prendendo il primo elemento del vettore V[0] e sommandolo a V[1] e poi V[2] etc. e continuando con il secondo numero sommandolo con gli altri , e così via con il terzo.. io volevo visualizzare ogni somma parziale.. e quando due somme parziali sono uguali mi memorizzo da un'altra parte, e incremento il numero di sottovettori che ovviamente parte da 1. Si beh la dovrei risolvere ricorsivamente, ma mi sembra un'impresa ardua..
La parte più difficile è in realtà la memorizzazione di questi valori. Di fatto si tratta di iterare lungo l'array e di sommare il valore attuale ad ogni somma parziale ottenuta fino a quel momento e di "unire quindi i due insiemi". Ci sono diverse problematiche comunque associate a questo tipo di soluzione:
1. L'occupazione di memoria è molto alta.
2. L'algoritmo non è molto veloce.
3. Che cosa te ne fai a questo punto delle somme parziali?
1. L'occupazione di memoria è molto alta.
2. L'algoritmo non è molto veloce.
3. Che cosa te ne fai a questo punto delle somme parziali?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo