1. #1
    Registered User
    Join Date
    Nov 2006


    Ok guys, i'm really stuck here.I have to write a greedy algorithm to solve the set covering problem.(i.e given a matrix nxn i have to find the best solution, which is a set of columns that covers all the rows). Anyway, istart from the empty solution and then i pick randomly a column. I have two vectors :

    map<int,vector<int> > covers; which gives me the rows that are covered by a column.For example covers[0].size() -> number of rows covered by column 0.

    map<int,vector<int> > covered_by; which gives me the columns that cover a row in the same way as above.

    and the add_column(int i) function

    Now, every column has a cost c. The best column to add to the set is te one that has max #rows(that covers)/cost c.

    What i have to do is in a loop running all the columns add the best ones by the above criterion and make the set but in every step i must subtract from the numerator the #rows that are already covered.

    Well, it doesn't seem very difficult but i'm really really stuck>i have tried everything.If anyone has an idea(the loop would be perfect)..please..It's very important.

    Last edited by joan; 12-05-2006 at 12:47 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM