求解貪婪演算法，貪婪演算法的基本思想

貪婪演算法基本思想是分層處理。

貪婪演算法是一種分層方法。 使用貪婪的禪宗信仰方法。

設計演算法的特徵是一步一步，根據一定的優化度量（可能是也可能不是目標函式），並且必須在每一步獲得區域性最優解。 每一步只考慮一條資料，其選擇應滿足區域性優化條件。 如果下一輪資料不再是可行的解決方案，如果無法再將資料與偏優解決方案連線起來，則在列舉所有資料之前，不會將資料新增到部分解決方案中，或者無法新增更多資料。

貪婪演算法可以解決的大多數問題通常具有以下特點：

1. 隨著演算法的進展，將累積另外兩組：一組包含已考慮和選擇的候選者，另一組包含已考慮但被丟棄的候選者。

2.有乙個功能可以檢查一組候選對是否為問題提供了解決方案。 此功能不考慮解決方法是否最佳。

3.還有乙個功能可以檢查一組候選物件是否可行，即是否可以在集合中新增更多的候選物件來獲得解決方案。 與前面的函式一樣，此時不考慮解決方案的最優性。

4. 選擇功能可以指示哪個剩餘的候選物件是最有希望解決問題的物件。

5. 最後，目標函式給出了解的值。

在一定的標準下，優先考慮符合標準的樣本，最後考慮不符合標準的樣本，最後得到答案的演算法稱為貪婪演算法。

也就是說，解在某種意義上是區域性最優的，而不考慮整體最優。

區域性最優 -？總體最佳。

有些專案需要占用會議室進行演示，會議室不能同時容納兩個專案。 給定每個專案的開始時間和結束時間（為您提供一系列特定專案），您可以安排演示的時間表，並要求會議室進行最多的演示。 回到這個數量最多的講道。

將一根金條切成兩半的成本與相同長度的銅板相同。 例如，一根長度為20的金條，無論切成兩半多長，褲凳都要花費20塊銅板。

一群人要分整根金條，怎麼分最經濟的銅板？ 例如，給定乙個陣列，總共代表三個人，整個金條的長度為 10+20+30=60。 金條分為三部分：10、20 和 30。

如果將長度 60 bar 分成 10 和 50，則成本為 60; 將 50 根金條的長度分成 20 和 30，成本為 50; 它總共花費了 110 塊銅板。 但是如果把60根金條的長度分成30根，胡維30根，就要花60根; 然後將長度30的金條分成10和20，並花費30粗鏈; 它總共花費了 90 塊銅板。

輸入乙個陣列，該陣列返回拆分的最小成本。

輸入：正陣列成本

正利潤

正 k，正 m

含義：成本[i]表示專案I的成本。

利潤[i]表示專案I在扣除費用後仍可賺取的金額（利潤）

k 表示您最多只能在序列中執行 k 個專案。

m 表示您的初始資金。

輸出：您最終獲得的最大金額。

所謂貪婪選擇屬性，是指通過一系列區域性最優選擇，可以選出問題的總體最優解，也就是說，在考慮做出什麼選擇時，我們只考慮當前問題的最優選擇，而不考慮子問題的結果。 這是貪婪演算法可行的第乙個基本要素。 貪婪演算法以迭代方式進行連續的貪婪選擇，每個貪婪選擇將所需問題簡化為更小的子問題。

要確定特定問題是否具有貪婪選擇的性質，有必要證明在每一步中做出的貪婪選擇最終導致了問題的總體最優解決方案。

當乙個問題的最優解包括其子問題的最優解時，該問題被稱為具有最優子結構的性質。 問題的最優子結構是貪婪演算法可以解決的問題的關鍵特徵。

需要注意的是，貪婪演算法並非完全不可用，一旦貪婪策略被證明是正確的，它就是一種高效的演算法。 例如用於查詢最小生成樹的 prim 演算法和 kruskal 演算法都是漂亮的貪婪演算法

貪婪演算法仍然是最常見的演算法之一，這是由於其簡單易行，構建貪婪策略並不是很困難。

不幸的是，它需要先得到證明，然後才能應用於問題的演算法。

一般來說，貪婪演算法的證明圍繞著這樣乙個事實，即整個問題的最優解必須從貪婪策略中存在的子問題的最優解中獲得。

對於示例中的 3 種貪婪策略，它們都無法建立（無法證明），解釋如下：

貪婪策略：選擇最有價值的乙個。 反例：

w = 30 項：a b c

重量： 28 12 12

值： 30 20 20

根據策略，先選擇A項，然後不能選擇，但最好選擇B和C。

2）貪婪策略：選擇權重最小的。它的反例與第一種策略相似。

3）貪婪策略：選擇每單位重量價值最高的物品。反例：

w = 30 項：a b c

重量： 28 20 10

值： 28 20 10

根據策略，三個專案的單位權重值相同，程式無法根據現有策略做出判斷，如果選擇A，答案不正確。 但是，如果在單位值相同時，優先使用小權重的條件中加入一句話，就可以解決這樣的問題。

所以需要注意的是，貪婪演算法可以和隨機化演算法一起使用，就不多說具體的例子了。 （因為這類演算法的普及度不高，技術含量也非常高，所以需要通過一些反例來判斷隨機物件是什麼，隨機性程度如何，但也是草稿狀態不能保證它完全正確，只能是最大狀態的概率景博是正確的）。