如何找到與指定N切口

Question

假設我們給出無限長度的杆，我們還給出N個段，例如[L1，L2）一個無限杆的分段的最大數。 這意味着我們可以在L1和L2之前切割杆以獲得一個片段。一些片段可能會重疊。

例如我們得到N = 4和

[2,3) 
[1,9) 
[4,5) 
[5,8) 

We can chose 

[2,3) 
[4,5) 
[5,8) 

段以獲得最大的三個區段。我不知道是否有任何知名的好算法？如果有的話，請給我建議。我可以手動完成，但不能得到一個好的工作算法。

Answer 1

按終點排序。

迭代片段，挑選不會與前一片段重疊的片段（可以通過簡單地跟蹤最後一個端點並檢查起始點在該點之後進行檢查）。

這將始終提供最佳解決方案。

對於你的榜樣，整理後，我們有：

[2,3) 
[4,5) 
[5,8) 
[1,9) 

然後我們通過[2,3)，[4,5)，[5,8)和[1,9)，採摘所有的人除了[1,9)。

爲什麼這是最佳

顯然具有最小終點段將是我們的選擇之一，因爲它的任何部分重疊將有更大的終點，從而可以用更多的段重疊起始於一個更大的值，任何數據段B與重疊具有最小終點也將與具有任何段重疊重疊段A，因此B不能小於A.

一個更好的選擇從這裏，我們重複這個參數，使下一個段的最小端點與上一個端點不重疊，直到我們到達最後。

Answer 2

這實際上是動態編程對貪婪編程的最常見的例子之一。 實際上，我可以給你什麼比這更鏈接：http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/ 它會告訴你動態的方式來做到這一點。 Dakeling答案是一個貪婪的算法。

動態和貪婪有什麼區別？ 讓我告訴你，在金錢上。 假設您有$ 123，並有$ 1，$ 2，$ 5，$ 10，$ 20，$ 50的賬單。如何用最少的費用做到這一點？

貪婪總是拿起此刻的最佳選擇。它會得到在給定時刻可以採取的最大法案。因此，首先將採取50，然後50，然後20，然後2，然後按1

但是，如果我們有一個像100，$ 1，$ 99 $ 24鈔票？ 貪婪首先需要100，然後會花費1 23美元。

什麼動態所做的是分析當前的決定，基於之前做出的決定和糾正不適當的過去的決定。這樣你總能得到最少量的硬幣。 （http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/）

所以： 動態：

• 慢
• 總是準確
• 更難

貪婪：

• 直截了當
• 並不總是準確的（猜測爲什麼只有$ 1，$ 2，$ 5和這些乘以10：d）
• 快速