Solved
How do you cover an entire set?
Posted on 2011-02-26
Hey,
I had a question that kept bugging me after my last algorithms class. My professor asked us to come up with an algorithm that will select as few subsets as possible to re-make the original set. And I came up with this:
We would take the largest subset with the most elements that are present in the original set, and then cancel out the elements in the original set, and then we would repeat this process till all the elements in the original set are cancelled out.
But he said that it wasn't the optimal solution... and didn't give me a good enough explanation...
I don't understand why this solution isn't the most optimal one... because even if you had a set S = {1, 2, 3, 4, 5}, and subsets S1 = {1, 2}, S2 = {2, 3, 4}, S3 = {1}, S4 = {5}. With my algorithm you would select S2, S3, and S5... right? Which would remake the original set.
Could someone help me understand this?