经典SCP描述包含一个集合U以及U内元素构成的若干各小类集合S，目标是找到S 的一个子集，该子集满足所含元素包含了所有的元素且使小类集合个数最少。例如，U={1,2,3,4,5}，S={ {1,2},{3,4},{2,4,5},{4,5}},找到集合能满足条件的可以有O={ {1,2},{3,4}{4,5}}或是O={ {1,2},{3,4},{2,4,5}}，至于具体选哪种组合，还有引申的一个问题：WSC，即Weighted Set Cover加权集合覆盖，每个集合类被赋予不同的权值，从而由权值决定最终的选择。
转载文章：Set Cover Problem(集合覆盖问题)