算法從給定的數據集中找到最優解

Question

假設我有一個給定的數據集。

4 → a b c 
5 → l b d 
6 → e b c 
42 → l b c 

這裏的數據項在組中，使得它們的組合值在第一列中給出。爲了更加準確，這些項目以不同的方式進行分組。

該算法的輸入應該是項目。 輸出應該是最好的組合，通過它我們可以以最小的成本獲得所有項目集。

例子。
要獲得b,c,l和e的值，我們需要採用行的密鑰爲5，行的密鑰爲6。返回5和6的總和。

programm b c l e 
    output: 11 = 5+6 

在這裏，我們必須返回4+5 = 9。雖然關鍵字42的行也符合標準9 < 42。

programm l b c 
    output: 9 = 4+5 

programm e b c 
    output: 6 

Answer 1

顯然，您可以從不屬於查詢集的組中移除元素。然後，剩下的是加權Set Cover問題。這是NP難，因此難以優化解決。可能greedy heuristic就足夠了;如果你真的需要一個最佳的解決方案，我會先嚐試調查你的輸入實例是否有可能被利用的屬性，或者使用ILP求解器。