假設有 m(m<100) 個集合并且元素限制為 1-n(n<100)。我正在尋找一種演算法來找到覆寫最多元素的集合組合，并且任何兩個集合都沒有交集。
例子：
輸入： [{1,2,3},{2,4},{3,5}]
輸出： [{2,4},{3,5}]
如果有比 O(2^m) 更好的解決方案？
uj5u.com熱心網友回復：
讓我按照我的理解重述這個問題。
你有一組集合。你想找到一個沒有兩個集合相交的子集合，它的并集盡可能大。
這個優化問題是一個 NP-hard 問題，因此每個已知演算法都是m. 這可以通過限制到每個集合有 3 個元素的特殊情況來看出。那就是3維匹配問題。決策變體是“找出你是否至少可以覆寫k元素”。決策變體在 Karp 的 21 個 NP 完全問題的原始串列中。
為什么優化版本 NP-hard 和決策版本 NP-complete？這是因為沒有簡單的方法來驗證聲稱的最優子集集實際上是最優的。但是很容易驗證至少涵蓋k元素的不相交子集的集合就是您所聲稱的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/496604.html
標籤：算法
下一篇：MYSQL按重量匹配樣本