Set Cover Problem

Discussion in 'General Computer Support' started by sarah2248, Dec 1, 2010.

  1. sarah2248

    sarah2248

    Joined:
    Dec 1, 2010
    Messages:
    1
    I am working on the set cover problem and I would really appreciate some help.

    I wanted to create another java program which does the following:

    Input: different sizes of sets and the universe, let’s say that the universe contains elements 1 through 100.
    The program will create all the combinations of sets to find out what is the smaller number of sets that cover the universe. Following is an example:

    U={1,2,3,4,5,6,7,8,9,10}
    s1={1,2,3,8,9,10}
    s2={1,2,3,4,5}
    s3={4,5,7}
    s4={5,6,7}
    s5={6,7,8,9,10}
    The program will generate all the combinations of the above sets. It will start with individual sets, and then it will make all possible combinations of two sets, then three,..... For the above example, it will generate 32 sets.

    and then it will output that set2 and set5 cover the universe.

    I was wondering if anyone could help me write the algorithm or pseudo code for the above example, so that I can write a java program based on that. I already wrote a program based on the greedy method. For some reason, I can not figure out how to start writing this program and If someone could show me the algorithm/pseudo-code, I would greatly appreciate it. Thanks so much in advance.

    This is what I wrote so far:
    for size in 1..|S|:
    combination(S, n) //this creates cobinations of n with the subesets of C
    if(union(c)==universe)
    then return C.

    As you can see, I have no idea how to design an algorithm. Please help me write this algorithm.
    sarah2248, Dec 1, 2010
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. zxcvar
    Replies:
    0
    Views:
    782
    zxcvar
    Dec 28, 2003
  2. Jamin

    Shutter cover problem Sony DSC P72 - fixable?

    Jamin, Jan 28, 2004, in forum: Digital Photography
    Replies:
    0
    Views:
    554
    Jamin
    Jan 28, 2004
  3. Feck
    Replies:
    2
    Views:
    514
  4. rolling

    nero cd cover problem?

    rolling, May 9, 2005, in forum: NZ Computing
    Replies:
    0
    Views:
    627
    rolling
    May 9, 2005
  5. HiBob
    Replies:
    0
    Views:
    806
    HiBob
    May 27, 2008
Loading...

Share This Page