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.
Thanx
