獲得最大的整數子集具有一定的最小距離/差異

Question

我有一整數集或例子：{1,3,4,5,10}現在我想要最大（最大=大多數元素）子集其中每個元素都有與每個其他元素的最小距離/差異。

例如與Set {1,3,4,5,10}和最小距離2的結果可以是：

{1,3,5,10}

或距離3 ：

{} 1,5,10

做了（好/高效）算法存在解決這個問題？

Answer 1

這絕對不是NP完全問題。

其實這是一個經典的Interval Scheduling問題的一個特例，而在正常區間調度問題，長度不固定

在你的問題

在這裏，您可以查看每個數字是時間間隔的開始時間，每個間隔都有你的「最小距離」作爲間隔長度。

每個間隔具有一個完成時間，其是開始時間+間隔長度

所以解決方案將是

1排序全部結束時間的時間間隔。

2按排序順序依次遍歷它們，將結果集添加到與結果集中所有現有時間間隔兼容的結果集中。

該解決方案是最優的，並具有O（nlogn）時間複雜度。

您可以在上面的鏈接中找到關於其他貪婪算法的證明和信息。

Answer 2

沿着這些線：

1）對輸入進行排序。

2）通過輸入並使用它們將從集合中排除的元素的數量標記每個元素（如果它們被選擇的話）。

3）從可用元素中依次選擇具有最低標記的元素。

4）刪除排除的元素。

5）重複3），4）

所以，在你的例子：

1 3 4 5 10  - difference 3 

第一步已經完成，將步驟2中，我們得到：

1 3 4 5 10 
1 3 2 2 0 

說明 - 如果我們選擇1，我們排除1號-3;如果我們選擇3，我們排除3號1,4和5，等等...

下一步：

• 選10，刪除什麼。 - 1 3 4 5 (10)
• 選1，刪除3 - (1) 4 5 (10)
• 選4（或5），除去5（或4） - 1 4 10

我不保證這個作品，但它是一個開始。 ..

Answer 3

是的，下面的貪婪算法給出了最優解。按照排序順序掃描整數，如果前一個整數足夠遠，則取整數。正確性遵循一個感應證明，對於每個解S和每個整數u，貪婪解決方案選擇至少與S一樣多的整數≤ u。作爲S.