假設(shè)你辦了個廣播節(jié)目，要讓全美50個州的聽眾都收聽得到。為此，你需要決定在哪些廣播臺播出。在每個廣播臺播出都需要支付費(fèi)用，因此你力圖在盡可能少的廣播臺播出。

聽起來很容易，但其實(shí)非常難。具體方法如下。
(1) 列出每個可能的廣播臺集合，這被稱為冪集 （power set）。可能的子集有2 n 個。
(2) 在這些集合中，選出覆蓋全美50個州的最小集合。

無法求出最優(yōu)解

近似算法，貪婪算法可化解危機(jī)！使用下面的貪婪算法可得到非常接近的解。

NP完全問題

為解決集合覆蓋問題，你必須計(jì)算每個可能的集合。
你需要計(jì)算所有的解，并從中選出最小/最短的那個

如何識別NP完全問題

元素較少時算法的運(yùn)行速度非常快，但隨著元素?cái)?shù)量的增加，速度會變得非常慢。涉及“所有組合”的問題通常是NP完全問題。

不能將問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。

如果問題涉及集合（如廣播臺集合）且難以解決，它可能就是NP完全問題。

如果問題可轉(zhuǎn)換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題。