最小分組算法

Question

我有一組值，每個值都有一個可能的組。 值可以重複，但在不同的組。

什麼將是一個最佳的算法，得到基團的最小數目

樣品組： （12，b）組 （38，A組） （12，A組）

期望結果： （38，A組） （12，A組）

（只有一個組用於）

- 編輯： 我需要一個算法從上面的例子中找到一組最小數量的組。 如果我想有一個壞的算法將選擇 （12，b組） （38組） 這2組進行相同的價值觀，而不是使用一個，不是我想要的

Answer 1

如果我沒有理解正確的問題，這是Set cover problem

鏈接中描述的貪婪算法從組a開始，然後終止，因爲這已經涵蓋了所有。

請注意，一般而言，它只會產生最佳解決方案的近似值。