Salve a tutti.
Ho un importante progetto da consegnare a giorni; tale progetto verrà valutato dalla piattaforma automatica online Domjudge, che verificherà se la mia soluzione è efficiente o meno.
La richiesta della traccia è quella, data una sorta di catena di montaggio con N lavori da far eseguire a K persone, di dividere tale lavoro in K parti in modo tale che la differenza della somma tra tutte queste ultime sia minima.
In un primo momento ho adottato un approccio brutal force, che consiste nel trovare tutte le possibili combinazioni di K cifre in modo tale che la loro somma sia uguale ad N, ad esempio:
se N=6 e K=3, allora le combinazioni saranno (4,1,1) (3,2,1) e (2,2,2).
Tali combinazioni, nel caso in cui vi sia almeno un valore diverso da tutti gli altri, devono essere permutate in modo da valutare trovare la soluzione superottima; ad esempio:
Sempre avendo N=6, K=3 e l'array [20 19 20 20 21 19], le combinazioni da tenere in considerazioni saranno le seguenti:
{4,1,1} {1,4,1} {1,1,4} {3,2,1} {3,1,2} {2,3,1} {2,1,3} {1,2,3} {1,3,2} {2,2,2}
Ovviamente tale operazione è inutile quando gli elementi contenuti nell'array sono tutti uguali tra di loro.
La scelta della soluzione superottima si basa sul calcolo delle somme dei vari subarray in base alle combinazioni trovate, scegliendo quella con differenza minima tra subarray di valore massimo e subarray di valore minimo, aggiornando ogni volta un valore diff_min e copiando, quando verificato, tale soluzione ottima in un vettore d'appoggio.
Esempio: date le precedenti combinazioni, la soluzione superottima risulterà essere {2,2,2}, pertanto l'array verrà splittato nel seguente modo: [20 19 | 20 20 | 21 19].
Voi direte adesso: dov'è che sta il problema? Il problema è che tale procedimento risulta essere corretto per partizioni di numeri piccoli, mentre per numeri grandi mi porta a consumare una notevole quantità di memoria che causa un segmentation fault e, pertanto, mi fa risultare il progetto errato.
Dopo tutta la fatica che ci ho buttato, mi dispiacerebbe non poter presentare tale lavoro per un problema di segmentation fault, che sto cercando di fixare in tutti modi, quindi chiedo a voi forumini di venirmi gentilmente in aiuto.
N.B. L'ordine dei valori dell'array non può essere alterato nè tantomeno posso usare un numero maggiore o minore di split in base a quanto specificato.
Qui il codice:
codice:#include <iostream> #include <climits> #include <vector> #include <string> #include <algorithm> using namespace std; bool uguali(vector<unsigned> v) //VERIFICO SE GLI ELEMENTI DEL VETTORE SONO UGUALI { for (int i=1; i<v.size(); i++) { if (v[0]!=v[i]) { return false; } } return true; } int somma(vector<unsigned> p) //SOMMO GLI ELEMENTI DI P DA 1 A N-1 { int s=0; for (int i=1; i<p.size(); i++) { s+=p[i]; } return s; } bool valuta(vector<unsigned> p,vector<unsigned> v,unsigned& diff_min,vector<unsigned> somme)//VALUTA LA SOLUZIONE SUPER OTTIMA { int s=0,index=0; //INDICI UTILI ALLA SOMMA for(int i=0; i<p.size(); i++) //SOMMO LE CIFRE DEL VETTORE IN MODO TALE DA RISPETTARE QUANTO ILLUSTRATO IN P { for (int j=0; j<p[i]; j++) { s+=v[index]; index++; } somme.push_back(s); s=0; } int massimo=(*max_element(somme.begin(),somme.end())); //TROVO MASSIMO E MINIMO DEL VETTORE SOMME int minimo=(*min_element(somme.begin(),somme.end())); if (massimo-minimo<diff_min) //SE LA DIFFERENZA TRA MAX E MIN E' OGNI VOLTA PIU' PICCOLA { diff_min=(massimo-minimo); //AGGIORNO DIFF_MIN E RITORNO TRUE return true; } return false; } void genera_valuta_partizioni(unsigned n,unsigned amici,vector<unsigned> Materia,vector<unsigned>& risultato) //GENERA LE PARTIZIONI, INVIANDOLE A "VALUTA" { //FUNZIONE SIMILE A QUELLA DI SOTTO, ECCETTO PER L'ASSENZA DELLE PERMUTAZIONI vector<unsigned> p(amici,1); p[0]=(n-amici+1); vector<unsigned> somme; int tmp=0; unsigned diff_min=INT_MAX; while (true) { if(valuta(p,Materia,diff_min,somme)) { if (!risultato.empty()) { risultato.clear(); } risultato=p; } for (int i=1; i<amici; i++) { if (p[i]<p[0]-1) { tmp=i; break; } } if (tmp==0) { return; } for (int i=1; i<=tmp; i++) { p[i]=p[tmp]+1; } p[0]=(n-somma(p)); tmp=0; } } void genera_permuta_valuta_partizioni(unsigned n,unsigned amici,vector<unsigned> Materia,vector<unsigned>& risultato)//GENERA E PERMUTA LE PARTIZIONI, INVIANDOLE A "VALUTA" { vector<unsigned> p(amici,1); //vettore iniziale inizializzato tutto ad 1 p[0]=(n-amici+1); //inizializzo la prima cella del vettore a n-amici+1 vector<unsigned> somme; //vettore di appoggio per calcolare le varie somme nella funzione "valuta" int tmp=0; //variabile temporanea per memorizzare l'indice nel while unsigned diff_min=INT_MAX; //variabile da aggiornare ogni qual volta trovo una funzione superottima while (true)// PEZZO DI CODICE ERRATO PER SEGMENTATION FAULT---> SI OCCUPA DI PARTIZIONARE UN INTERO E POI PERMUTARE E VALUTARE LE SOLUZIONI { do //INIZIO BLOCCO PER LE PERMUTAZIONI { for (int i=0; i<p.size(); i++) //STAMPA CHE IN LOOP OGNI QUAL VOLTA COMINCIO A CALCOLARE PARTIZIONI DI NUMERI GRANDI { cout<<p[i]<<" "; } cout<<endl; if(valuta(p,Materia,diff_min,somme)) //SE VALUTA E' VERA { if (!risultato.empty()) //RIPULISCO IL VETTORE RISULTATO SE E' PIENO { risultato.clear(); } risultato=p; //ASSEGNO P A RISULTATO cout<<endl<<endl<<"PRESO!"<<endl<<endl; } }while(prev_permutation(p.begin(),p.end())); for (int i=1; i<amici; i++) //TROVO L'INDICE PER IL QUALE RISULTI CHE P[I] SIA MINIMORE DI P[0]-1 { if (p[i]<p[0]-1) { tmp=i; break; } } if (tmp==0) //SE TMP RIMANE A 0, ALLORE NON VI SONO INDICI DEL GENERE E POSSO TERMINARE IL CICLLO { return; } for (int i=1; i<=tmp; i++) //ASSEGNO NUOVI VALORI AI VALORI DI P DIVERSI DA P[0] { p[i]=p[tmp]+1; } p[0]=(n-somma(p)); //A P[0] DO UN VALORE IN MODO TALE DA RISPETTARE IL VINCOLO <=N tmp=0; //RESETTO LA VARIABILE TEMPORANEA } } int main() { unsigned n,amici,index=0,sum=0;// dichiaro numero di Materia, numero di amici e due variabili che serviranno per la stampa vector<unsigned> risultato; //vettore iin cui viene memorizzato il modo di dividere il vettore Materia string s; //stringa s per iniziare il ciclo (sempre!=-1) cin>>s; if (s!="-1") { cin>>s; } while (s!="-1") { cin>>n>>amici; //inserisco da input vector<unsigned> Materia(n); //dichiaro vettore di Materia for (int i=0; i<n; i++) { cin>>Materia[i]; //riempio } if (uguali(Materia)) //se gli elementi in Materia sono uguali { genera_valuta_partizioni(n,amici,Materia,risultato); //genero le partizioni del numero di elementi (ad esempio, per 6 saranno 4-1-1 , 3-2-1, 2-2-2) senza permutarle } else //altrimenti { genera_permuta_valuta_partizioni(n,amici,Materia,risultato); //le genero con la permutazione (e qua son cazzi) } sum+=risultato[index]; cout<<"result "<<s<<endl; //blocco stampa for (int i=0; i<n; i++) { if (i==sum) { cout<<"|"<<" "; index++; sum+=risultato[index]; } cout<<Materia[i]<<" "; } risultato.clear(); //ripulisco vettore risultato Materia.clear(); //e vettore Materia per altra ciclata cin>>s; if (s!="-1") { cin>>s; } index=0; //resetto le variabili sum=0; } return 0; }
Rispondi quotando
