Difference between revisions of "TADM2E 1.6"
From Algorithm Wiki
m (Blanked the page) |
|||
| Line 1: | Line 1: | ||
| + | Let <math>U=\{1,2,3\}</math> and S consists of <math>S_1=\{1,2,8,4,10\}</math>, <math>S_2=\{1,3,6,9\}</math>, <math>S_3=\{1,2,3\}</math>. The algorithm would give an answer of <math>S_1</math>, <math>S_2</math> but the correct answer is <math>S_3</math> because it has the fewest elements and covers <math>U</math>. | ||
| + | The algorithm would remove elements <math>\{1,2\}</math> (members of <math>S_1</math> is the largest subset in <math>S</math>. Then chose <math>S_2</math> because it is the next largest and remove element <math>\{3\}</math>. The algorithm would exit because <math>U</math> is empty. However, <math>S_3</math> is the correct answer. | ||
Revision as of 22:41, 27 May 2019
Let $ U=\{1,2,3\} $ and S consists of $ S_1=\{1,2,8,4,10\} $, $ S_2=\{1,3,6,9\} $, $ S_3=\{1,2,3\} $. The algorithm would give an answer of $ S_1 $, $ S_2 $ but the correct answer is $ S_3 $ because it has the fewest elements and covers $ U $.
The algorithm would remove elements $ \{1,2\} $ (members of $ S_1 $ is the largest subset in $ S $. Then chose $ S_2 $ because it is the next largest and remove element $ \{3\} $. The algorithm would exit because $ U $ is empty. However, $ S_3 $ is the correct answer.
