貪心算法還是動態規劃？

給出了列表l = [x_1，...，x_n]。名單中的每一個元素都是某塊木頭的長度。要粘合長度爲a和b的兩塊木頭，您需要最大（a，b）的膠水。膠合後，你得到一塊長度爲a + b的木頭。計算最小膠量來粘合所有的部分。貪心算法還是動態規劃？

你認爲貪婪算法在這裏工作嗎？我想不出任何例子。說貪婪算法我的意思是：拿兩塊最小長度的膠粘它們，直到所有塊都粘在一起。使用一些優先級隊列，這可以在O（n log n）複雜度中完成。

這是否行得通？如果沒有，請給我一些列表l的例子，它可以粘在比貪婪算法要少的膠水中。

來源

2016-01-12 piternet

粘合2件是否會增加長度？ – SGM1

你的意思是？當你粘合兩段長度a和b時，你會得到新的長度a +長度b。 – piternet

兩根棍子可以粘在一起，這就是爲什麼我問。在這種情況下，恕我直言，膠水的數量取決於長度。 – SGM1

貪婪算法並不總是最優的。一個反例是[1,2,2,3]，貪婪算法將使用10個單位的膠水，最優化將使用9個單位。

貪心算法：

1-2 = 2 glue 
2-3 = 3 glue 
3-5 = 5 glue 
--------------- 
total = 10 glue

優化：

2-2 = 2 glue 
1-3 = 3 glue 
4-4 = 4 glue 
-------------- 
total = 9 glue

動態規劃是。

來源

2016-01-12 22:48:40 Briguy37

「動態編程它」你能詳細說明一下你想要的算法嗎？ – AndyG

你知道這個動態算法是如何工作的嗎？ – piternet

看起來好像有沒有最優貪婪算法和沒有一般的動態規劃解決方案。我認爲這是NP-hard，我解釋了原因。

讓我們來分析問題。我們有N個元素。將這個集合分成兩個子集，分別是X和Y元素。首先，我們粘貼X子集中的所有元素，然後以某種方式粘貼Y子集中的所有元素（如分割和征服技術）。並且在最後的粘閤中，我們應該粘合代表X和Y子集的2個元素。我們在最後一次粘貼中需要的最小量的膠水是多少？當X元素和Y元素的和的差值最小時！我們將此問題表示爲遞歸分區問題這是NP難以自行修復的問題

來源

2016-01-13 15:59:55 valdem

貪心算法還是動態規劃？

回答

相關問題