# Minimization Problem

• Aug 10th 2007, 01:05 AM
viswastone
Minimization Problem
Hi
I have the following structure. I have 5 files. Each file can have n number of files. Totally i have 10 subfiles. Now, i want to find the minimum number of Files so that all subfiles will be included.

For eg:

File Sub Files
A 1 2 3 8
B 2 4 6 10
C 1 3 5 7 8 9
D 7 9 10
E 1 3 7 9

If i combine B and C all the 10 subfiles will be handled. 1,2,3,4,5,6,7,8,9,10.
I think that is the minimun combination to cover all sub files. Is there any algoirthm to find this? Actually in my problem to develop a tool, I can have n number of files and n number of subfiles. Please tell me how to find the minimum number of files required to cover all the files. Which concept can be used for this case ?

Thanks.
• Aug 11th 2007, 08:56 AM
CaptainBlack
Quote:

Originally Posted by viswastone
Hi
I have the following structure. I have 5 files. Each file can have n number of files. Totally i have 10 subfiles. Now, i want to find the minimum number of Files so that all subfiles will be included.

For eg:

File Sub Files
A 1 2 3 8
B 2 4 6 10
C 1 3 5 7 8 9
D 7 9 10
E 1 3 7 9

If i combine B and C all the 10 subfiles will be handled. 1,2,3,4,5,6,7,8,9,10.
I think that is the minimun combination to cover all sub files. Is there any algoirthm to find this? Actually in my problem to develop a tool, I can have n number of files and n number of subfiles. Please tell me how to find the minimum number of files required to cover all the files. Which concept can be used for this case ?

Thanks.

Brute force:

Code:

``` for file= A to E   if file contains all 10 files     return file   endif endfor   for file1=A to E   for file2 = fileAfter(file1) to E     if file1 union file 2 contains all 10 files       return file 1, file2     endif   endfor endfor   for file1=A to E   for file2 = fileAfter(file1) to E     for file3= fileAfter(file2) to E       if file1 union file2 union file3 contains all 10 files         return file 1, file2, file3       endif     endfor   endfor endfor   for file1=A to E   for file2 = fileAfter(file1) to E     for file3= fileAfter(file2) to E       for file4= fileAfter(file3) to E         if file1 union file2 union file3 union file 4 contains all 10 files           return file 1, file2, file3, file4         endif       endfor     endfor   endfor endfor   retuen A, B, C, D, E```
RonL
• Aug 17th 2007, 12:54 AM
viswastone
Thanks.
Hi, thanks for giving me the logic.:)