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.

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

Hi, thanks for giving me the logic.:)