Difference between revisions of "Help talk:Trolls on wheels!"
From Algorithm Wiki
Ridgemcghee (talk | contribs) |
Ridgemcghee (talk | contribs) |
||
| Line 5: | Line 5: | ||
The union of s3 and s4 cover all elements (2 sets). | The union of s3 and s4 cover all elements (2 sets). | ||
| − | However, there is a | + | However, there is a correct counterexample (see counterexample 2). |
Revision as of 09:05, 4 December 2014
The first counterexample shown is incorrect as greedy would get an optimal solution (2 sets). First, greedy would choose S3 since it contains 10 uncovered elements. However, then, greedy would choose S4 since it contains 6 uncovered elements (not s2 since it only contains 4 uncovered elements). The union of s3 and s4 cover all elements (2 sets).
However, there is a correct counterexample (see counterexample 2).
