• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Set Cover problem

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



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 share 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:


please help me write this algorithm. Thanks
 
lowercase baba
Posts: 13089
67
Chrome Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You've basically got your algorithm.

1) create all the possible set combinations
2) check each to see if a given combination covers the universe

if you have step 2 start with the smaller sets first (the one set combo, then the two set combos, etc), you can quit as soon as you find one.
 
Can you shoot lasers out of your eyes? Don't look at this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic