查找最小加權集

Question

我面對的是死路一條。已經搜索槽棧論壇，希望這個問題尚未問..

我有一個名爲UNIVERS U（與許多元素）。 我有含有來自U.幾個元素我們可以發現在不同的一組相同的元件N組。每個集合都有一個權重（與其包含的元素數量無關）。

我必須找到一個算法，發現套combinaison，其中最小權重，至少包含了所有從UNIVERS的元素。

我認爲它的常見的問題（也許一個衆所周知的NP結束於問題），但我不能告訴自己，這是不可能的。 我正在尋找一些優化，但不知道從哪裏開始說起。

任何建議？

親切的問候，

晏

Answer 1

這是Weighted set cover問題。這是NP-Complete。