[ Adnan Bosovic @ 14.06.2005. 18:16 ] @
Pozdrav, Imam jedno pitanje. Radim sa kombinacijama bez ponavljanja kod kojih nije bitan raspored elemenata, vec su permutacije {2 5 6 9} i {2 9 6 5} iste i nema potrebe da ih ponovo uzimamo u obzir nego cemo napisati onu kod koje su cifre sortirane. Prilazem i mali kod koji sluzi samo za primjer ovih permutacija. Code: #include <stdio.h> #define BROJKOMB 4 #define ODBROJ 8 char komb[BROJKOMB]; void print_c(char *array, int size){ int i; for(i=0;i<size;i++) printf("%d ",array[i]); printf("\n"); } void gen_c(char *array, int c, int broj, int od){ if(c == broj) print_c(array,broj); else for(array[c] = c?array[c-1]+1:1; array[c] <= od;array[c]++) gen_c(array,c+1,broj,od); } int main(){ gen_c(komb,0,BROJKOMB,ODBROJ); } Ovaj primjer generise 4 od 8 kombinacije. Interesuje me da li je moguce na gornjem primjeru izabrati neke kombinacije od po 4 broja tako da: ako nekih 6 od 8 brojeva slucajno odabranih bude "ukljuceno", a ostala dva budu "iskljucena" onda da budemo sigurni da ce biti odabrana jedna kombinacija od po 4 broja koja u kojoj ce svi brojevi imati stanje "ukljuceno". Potrebno je kombinacije 4 od 8 optimalizirati da ih bude sto manje. Ocigledno je da treba generisati sve 4 od 8 kombinacije i 6 od 8 a zatim gledati koje 4 od 8 kombinacije se najbolje uklapaju, odnosno najbolje pokrivaju sve 6 od 8 kombinacije. Ovi brojevi su koristeni samo za primjer, dok rjesenje zahtjeva opcenit slucaj. Ako se neko nece nasmijati, meni ovaj problem lici na problem ruksaka. Optimalno dodati kombinaciju, a zatim rijesiti podproblem. Nisam uspio da dokucim optimalnu strukturu ovog problema tj. nisam uspio da ga rastavim na podprobleme. Jako je tesko zapisati neko stanje u kome bi se sistem nalazio nakon sto bismo dodati neku kombinaciju. Ako neko ima ideju volio bih je cuti. Unaprijed hvala, Adnan Bosovic |