貪心演算法基本思想

① (三) 貪心演算法

貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。

假設有3種硬幣，面值分別為1元、5角、1角。這3種硬幣各自的數量不限，現在要找給顧客3元6角錢，請問怎樣找才能使得找給顧客的硬幣數量最少呢？

你也許會不假思索的說出答案：找給顧客3枚1元硬幣，1枚5角硬幣，1枚1角硬幣。其實也可以找給顧客7枚5角硬幣，1枚1角硬幣。可是在這里不符合題意。在這里，我們下意識地應用了所謂貪心演算法解決這個問題。

所謂貪心演算法，就是 總是做出在當前看來是最好的選擇(未從整體考慮) 的一種方法。以上述的題目為例，為了找給顧客的硬幣數量最少，在選擇硬幣的面值時，當然是盡可能地選擇面值大的硬幣。因此，下意識地遵循了以下方案：
（1）首先找出一個面值不超過3元6角的最大硬幣，即1元硬幣。
（2）然後從3元6角中減去1元，得到2元6角，再找出一個面值不超過2元6角的最大硬幣，即1元硬幣。
（3）然後從2元6角中減去1元，得到1元6角，再找出一個面值不超過1元6角的最大硬幣，即1元硬幣。
（4）然後從1元6角中減去1元，得到6角，再找出一個面值不超過6角的最大硬幣，即5角硬幣。
（5）然後從6角中減去5角，得到1角，再找出一個面值不超過1角的最大硬幣，即1角硬幣。
（6）找零錢的過程結束。
這個過程就是一個典型的貪心演算法思想。

貪心策略總是做出在當前看來是最優的選擇，也就是說貪心策略並不是從整體上加以考慮，它所做出的選擇只是在某種意義上的 局部最優解 ，而許多問題自身的特性決定了該問題運用貪心策略可以得到最優解或較優解。(註：貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。）

貪心演算法沒有固定的演算法框架，演算法設計的關鍵是 貪心策略的選擇 。選擇的貪心策略必須具備無後效性。

貪心策略 適用的前提 是：

嚴格意義上講，要使用貪心演算法求解問題，該問題應當具備以下性質：

注意 ：對於一個給定的問題，往往可能有好幾種量度標准。初看起來，這些量度標准似乎都是可取的，但實際上，用其中的大多數量度標准作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。

因此， 選擇能產生問題最優解的最優量度標準是使用貪婪演算法的核心 。

實際上，貪心演算法 適用的情況很少 。一般，對一個問題分析是否適用於貪心演算法，可以先選擇該問題下的幾個實際數據進行分析，就可做出判斷。

最優解問題大部分都可以拆分成一個個的子問題(多階段決策問題)，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。

貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。

動態規劃方法代表了這一類問題的一般解法， 自底向上 構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。

而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始( 自頂向下 )，選擇最優的路，一直走到底就可以了。

一個問題分為多個階段，每個階段可以有n種決策，各個階段的決策構成一個決策序列，稱為一個策略。
這兩種演算法都是選擇性演算法，在進行決策的選擇時：

前提是這個問題得具有貪心選擇性質，需要證明(數學歸納法(第一、第二))，如果不滿足那就只能使用動態規劃解決。(一旦證明貪心選擇性質，用貪心演算法解決問題比動態規劃具有更低的時間復雜度和空間復雜度。)

從范疇上來看：
Greedy ⊂ DP ⊂ Searching （貪心是動規的特例）
即所有的貪心演算法問題都能用DP求解，更可以歸結為一個搜索問題，反之不成立。

貪心演算法所作的選擇可以依賴於以往所作過的選擇，但決不依賴於將來的選擇，也不依賴於子問題的解，這使得演算法在編碼和執行的過程中都有著一定的速度優勢。如果一個問題可以同時用幾種方法解決，貪心演算法應該是最好的選擇之一。但是貪心演算法並不是對所有的問題都能得到整體最優解或最理想的近似解，與回溯法等比較，它的適用區域相對狹窄許多，因此正確地判斷它的應用時機十分重要。

一步一步地進行，常 以當前情況為基礎根據某個優化測度作最優選擇，而不考慮各種可能的整體情況 ，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。

它採用 自頂向下 ，以 迭代 的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以 貪心法不需要回溯 。

【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。

【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

② 哈夫曼編碼（貪心演算法）

參考： 哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不差派拿同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。

下面看一個例子：
假如我們有虛搭一個包含1000個字元的文件，每個字元佔1個byte(1byte=8bits)，則存儲這100個字元一共需要8000bits。這還是有一些大的
那我們統計一下這1000個字元中總共有多少種字元，原來需要8bit來表示一個字元，如果使用更少的位數來表示這些字元，則可以減少存儲空間。
假設這1000個字元中總共有a、b、c、d、e、f共6種字元，使用使用3個二進制位來表示的話，存儲這1000個字元就只需要3000bits，比原來更節省存儲空間。

或許還可以再壓縮一下：
根據字元出現的 頻率 給與字元 不等長 的編碼，頻率越高的字元編碼越短，頻率越低的字元編碼越長。
它不能像等長編碼一樣直接按固定長度去讀取二進制位，翻譯成字元，為了能夠准確讀取翻譯字元，它要求一個字元的編碼不能是另外一個字元的前綴。

假設a、b、c、d、e、f這6個字元出現的頻率依次降低，則我們可以給與他們這樣的編碼

假如字元的出現頻率如圖所示，按照這樣的編碼表示的話，總位數如圖，一共2100bits，更加節省空間了

貪心策略：頻率小的字元，優先入隊。

步驟：
1.將每一個字元作為節點，以出現頻率大小作為權重，將其都放入 優先隊列 中（一個最小堆）；
2.每次出隊兩個節點並創建一個父節點，使其權值為剛剛出隊的節點的權值和，並且為兩個節點的父節點（合並）。然後將這個樹入隊。
3.重復操作2，直到隊列中只有一個元素（此時這個元素表示形式應該為一個樹）時，完成創建。

創建好了樹，該怎麼編碼呢？
我們對一個哈夫曼樹，從父節點開始的所有節點，往左邊標0，右邊標1。那麼到達葉子節點的順次編碼就可以找到了。

C：字元集合
Q：優先隊列
EXTRACT-MIN：傳入一羨山個隊列，出隊最小的元素
INSERT：將z插入到Q中

當for循環結束之後，此時隊列中只有一個元素，就是我們需要的哈夫曼樹，最後返回此樹即可。

假設T樹已經是一個最優的樹，假設x、y的頻率小於等於最低處的a、b，然後交換x、a，y、b。

計算代價是否發生變化。
比如這里比較 T 變成 T 』 後代價是否變化，發現代價變小或不變。

同理T』到T』』，又因為T本來假設就是最優的，所以只能相等
所以T』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的

③ python裡面什麼是貪婪

Python裡面的貪婪演算法（又稱貪心演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，/不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。

貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

基本思路

思想

貪心演算法的基本思路是從問題的某一個初始解出發一步一步地進行，根據某個優化測度，每一步都要確保能獲得局部最優解。每一步只考慮一個數據，他的選取應該滿足局部優化的條件。若下一個數據和部分最優解連在一起不再是可行解時，就不把該數據添加到部分解中，直到把所有數據枚舉完，或者不能再添加演算法停止 。

④ 貪心演算法

平面點集三角剖分的貪心演算法要求三角剖分後邊的總長度盡可能小。演算法的基本思想是將所有的兩點間距離從小到大排序，依次序每次取一條三角剖分的邊，直至達到要求的邊數。以下是兩種貪心演算法的主要步驟。

3.2.2.1 貪心演算法1

第一步:設置一個記錄三角剖分中邊的數組T。

第二步:計算點集S中所有點對之間的距離d(p_i，p_j)，1≤i，j≤n，i≠j，並且對距離從小到大進行排序，設為d₁，d₂，…，d_n(n-1)/2，相應的線段記為e₁，e₂，…，e_n(n-1)/2，將這些線段存儲在數組E中。

第三步:從線段集E中取出長度最短的邊e₁存到T中作為三角剖分的第一條邊，此時k=1。

第四步:依次從E中取出長度最短的邊e_k，與T中已有的邊進行求交運算，如果不相交則存到T中，並從E中刪除e_k。這一步運行到S中沒有邊為止，即至k=n(n-1)/2。

第五步:輸出T。

該演算法中，第二步需要計算n(n-1)/2次距離，另外距離排序需要O(n²lgn)次比較。T中元素隨第四步循環次數的增加而增加，因此向T中加入一條新邊所需要的判定兩條線段是否相交的次數也隨之增加。如果第四步的前3n-6次循環後已經構成點集的三角剖分，那麼第四步循環所需要的判定兩條線段是否相交的次數為

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常數時間內可以判定兩條線段是否相交，因此該演算法的時間復雜性為O(n³)。

3.2.2.2 貪心演算法2

第一步:求點集的凸殼，設凸殼頂點為p₁，p₂，…，p_m，凸殼的邊為e₁，e₂，…，e_m。並將凸殼頂點按順序連接成邊的e_i加入T(三角剖分的邊集合)，並且e_i的權值被賦為1。凸殼內點的集合為S₁={p_m+1，p_m+2，…，p_n}。

第二步:從內部點S₁中任取一點p_i，求與p_i距離最近的點p_j，將線段 存入T。

第三步:求與p_j距離最近的點(除點p_i外)，設為p_k，並將線段 加入T，並將這些邊的權值設為1，而w_ij、w_jk和w_ki的值加1，即為2。邊的權值為2則表示該邊為兩個三角形共有。

第五步:對權值為1的邊(除e₁，e₂，…，e_m外)的兩個端點分別求與其距離最近的點，並將其連線(得到新的三角形)加入T，新三角形邊的權值加1。

第六步:對權值為1的邊重復上一步，當一條邊被使用一次其權值增加1，直到所有邊的權值均為2為止(除e₁，e₂，…，e_m外)。

貪心演算法2中，第一步耗費O(nlgn);第二步需要計算n-1次距離與n-2次比較;第三步求p_k要計算n-2次的距離與n-3次比較;第四步要進行(n-3)×3次的距離計算及(n-4)×3次比較;第五步至多進行n-6次的距離計算與n-7次比較;第六步到第五步的循環次數不超過3n-9;因此整個貪心演算法2的時間復雜性為

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

⑤ 什麼是貪心演算法

問題一：貪心演算法，這個貪心到底是什麼意思 貪心指目光短淺，只看到當前這一步的最優決策，而不考慮以後的決策。這樣的演算法只在特定的問題下是正確的。

問題二：哪些常見演算法屬於貪婪演算法？ 顯然KMP和FLOYD演算法不是貪心演算法，FLOYD演算法是使用了類似於動態規劃的思想，而KMP演算法則是對串的前綴進行去處理得到所有可能出現匹配的位置從而減少不必要的位移。貪心演算法可能還有很多，但是一般能用到的可能只有這些。在確定一個問題是否能用貪心來解決的時候應該線能夠證明在這里使用貪心演算法的正確性（詳見演算法導論）

問題三：求解一貪心演算法問題 最快回答那個不懂別亂說，別誤人子弟。
這題標準的貪心演算法，甚至很多時候被當做貪心例題
要求平均等待時間，那麼就得用 總等待時間 / 人數
所以只用關心總等待時間，
如果數據大的在前面，那麼後面必然都要加一次這個時間，所以按從小到大排。
給你寫了個，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 問題四：貪心演算法的基本思想是什麼？ 自己利益最大

問題五：貪心演算法是什麼？求教學，c語言 jb51/article/71144，裡面講得比較詳細

問題六：貪心演算法的基本要素是什麼，並簡單解釋其含義 您好，我看到您的問題很久沒有人來回答顫運，但是問題過期無人回答會被扣分的並且你的懸賞分也會被沒收！銷迅所以我給你提幾條建議：
一，你可以選擇在正確的分類下去提問，這樣知道你問題答案的人才會多一些，回答的人也會多些。
二，您可以到與您問題相關專業網站論壇里去看看，那裡聚集了許多專業人才，一定可以為你解決問題的。
三，你可以向你的網上好友問友打聽，他們會更加真誠熱心為你尋找答案的，甚至可以到相關網站直接搜索.
四，網上很多專業論壇以及知識平台，上面也有很多資料，我遇到專業性的問題總是上論壇求解決辦法的。
五，將你的問題問的細一些，清楚一些！讓人更加容易看懂明白是什麼意思!
謝謝採納我的建議! !

問題七：貪心演算法的特性 貪婪演算法可解決的問題通常大部分都有如下的特性：⑴隨著演算法的進行，將積累起其它兩個 *** ：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。⑵有一個函數來檢查一個候選對象的 *** 是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。⑶還有一個函數檢查是否一個候選對象的 *** 是可行的，也即是否可能往該 *** 上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。⑸最後，目標函數給出解的值。⑹為了解決問題，需要尋找一個構成解的候選對象 *** ，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的 *** 為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果 *** 中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到 *** 里。每一次都擴充 *** ，並檢查該 *** 是否構成解。如果貪婪演算法正確工作，那麼找到的第茄斗梁一個解通常是最優的。

⑥ 貪心演算法總結

做了這10道題，其實發現貪心演算法沒有什麼規律，要說有什麼共同特點就是都是由局部最優從而推出全局最優，每個題基本上都要考慮其局部最優是什麼，其全局最優是什麼，所以雖然都用到了貪心演算法的思想，但是題與題之間又沒有什麼規律可言。

現在把這10道題的思路總結一下（總結主要以我的主觀看法在寫，可能別人看會不知道我在說什麼）

1.分發餅干：

https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

思路：想要完成最多的小孩滿足，那麼就得最小的餅干給胃口最小的小孩

這里的貪心思想，

局部最優就是盡可能讓一個餅干喂飽一個

全局最優就是最多的小孩滿足

2.擺動序列：

https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

思路：這里要找到最長的擺動序列，那麼其實就是找那些波峰波谷，如圖所示

可以看出來，在到達波峰波谷的路上有幾個數字不會影響什麼，可以直接去掉。

那麼這里的局部最優就是把單調坡上的點刪掉，保留最多的波峰波谷

全局最優就是得到對多的波峰波谷，即最長的擺動序列

3.最大子序和

https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

這道題顯然可以暴力解出來，即列出所有子序和，找出最大的，不過計算量會比貪心大很多。

這里主要介紹貪心解的思想：

想要得到最大子序和，就得保證每次相加時，相加後不能為負數，因為負數繼續往下加一定是拉低總和的，那麼我們當加成到負數時就重新從下個數開始加，並實時記錄最大的子序和，這樣一遍循環就能得出最大子序和。

局部最優：加成負數就立刻停止，並從下個元素重新開始

全局最優：得到最大子序和

4.買賣股票的最佳時機II

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

思路：想要得到最大利潤，那就要低價買入高價賣出，那麼怎樣的買賣才能得到最大利潤呢。

這里就體現出貪心演算法的「貪」字（我猜的），這道題貪在哪呢，貪在只要有利可圖就去做，即只要今天買入的價錢比明天賣出的價錢底，即有利可圖，那麼我就去做，做就是在今天買入，在明天賣出。

局部最優：得到每天的最大正利潤

全局最優：得到最大利潤

5.跳躍游戲

https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

思路：每個數組的元素代表的是可以跳的最遠下標，那麼我們只要使那個最遠下標包含最後一個下標就是可以跳到，那麼我們每跳到一個位置就要更新那個可以跳的范圍，即可以跳到的最遠下標。

局部最優：每次跳躍都得出最遠的跳躍范圍

全局最優：最後能跳到的最大范圍

6.跳躍游戲II

https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

思路：這道題要得到最小的跳躍數，其實只要保證跳的是位置是可以跳范圍內更新最遠范圍的位置就可以了。

為什麼這么說呢？以題例來說：

我們剛開始在『0』的位置，我們能跳到『1』和『2』的位置，那麼我們怎麼跳呢？可以看到跳到『1』之後更新的最大范圍是『4』，跳到『2』之後更新的最大范圍是『3』，所以我們就跳『2』了，因為跳『1』之後更新的最大可跳范圍更大包含了跳『2』的最大可跳范圍，那麼肯定是跳『3』最優呀，這里就體現了局部最優的思想。

局部最優：每次跳後，更新的最大可調范圍最大

全局最優：跳躍次數最少

7.K次取反後最大化的數組和

https://programmercarl.com/1005.K%E6%AC%A1%E5%8F%96%E5%8F%8D%E5%90%8E%E6%9C%80%E5%A4%A7%E5%8C%96%E7%9A%84%E6%95%B0%E7%BB%84%E5%92%8C.html

思路：想要得到最大數組和，我們就可以想到怎樣做呢？

一，盡可能保證負數最少

二，負數絕對值大的優先變正

三，正數絕對值小的優先變負，有零變零

本著這三條原則做，就能做出來。

那麼這道題體現了什麼貪心思想呢？

我感覺，前面那三條都是貪心中『貪』的體現

在負數中，局部最優就是：絕對值大的負數優先變正

在正數中，局部最優就是：絕對值小的正數變負，有零變零

得到的全局最優：數組和最大

8.加油站

https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html

思路：首先可以想到這道題是可以暴力解出來了，即分別以每個加油站為起點，得出可以跑一圈的加油站

那麼貪心思想做，該怎麼做呢，首先可以想到，如果以一個1點為起點當跑著跑著跑到3，油變為負數時，那麼說明以這個起點是不行的，但是以2或3為起點行不行呢？答案肯定是不行的，因為1跑到3，油變為負，說明1~3的gas=0的，所以可以得出，如果1~3油數變為負數，那麼由2~3油數肯定也為負數。

所以這里就可以得出，如果經過幾個加油站油數變為負了，那麼起點就更新為這一段路的下個加油站跑

局部最優：油量一旦為負，就從下個加油站重新跑

全局最優：得出可以跑一圈的加油站起點

9.分發糖果

https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html

思路：每個孩子至少一個，如果一個孩子比他旁邊的孩子優秀，就要比他旁邊的糖果多，這道題一旦兩邊都考慮很容易顧此失彼，所以我們就定義兩個循環，分別從左到右，從右到左去考慮，只要更優秀則比他旁邊的多1，如果已經多了就不用變了。

局部最優：保證優秀的孩子比他旁邊的孩子糖果多

全局最優：滿足題中條件，至少要發的糖果

10.檸檬水找零

https://programmercarl.com/0860.%E6%9F%A0%E6%AA%AC%E6%B0%B4%E6%89%BE%E9%9B%B6.html

思路：我們在找零時要遵守的規則一定是：

5 得5

10 得10減5

15 得15，優先減一個10減一個5  如果10塊沒有則減三個5

局部最優：以最少用的5塊的方式找零

全局最優：得到找零能否進行下去

⑦ 程序設計一課中提到的貪婪法基本思想是什麼啊

貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
貪婪演算法的一般方法
1、問題描述
它有n個輸入，而它的解就由這n個輸入的某個子集組成，只是這個子集必須滿足某些事先給定的條件。
2、約束條件 那些必須滿足的條件稱為約束條件。
3、可行解 滿足約束條件的子集稱為該問題的可行解。
4、目標函數 事先給定的衡量可行解優劣的量度標准，通常以函數的形式給出，稱為目標函數。
5、最優解 使目標函數取極值（極大或極小）的可行解，稱為最優解。
6、子結構模式 貪心技術中，問題的最優一般是原輸入的子集，獲取最優子集的貪心方法為子結構模式
7、有序模式 通過計算已有的判定而得出的最優條件，可以為下一步的判定提供依據，這種形式的貪心演算法稱為有序模式。
8、貪婪演算法求解思想（分步處理）
�8�4 根據題意，選取一種量度標准；
�8�4 然後按這種量度標准對這n個輸入排序，並按序一次輸入一個量。
�8�4 如果這個輸入和當前已構成在這種量度意義下的部分最優解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。
這種能夠得到某種意義下的最優解的分級處理方法稱為貪心演算法。

⑧ 5.貪心演算法的核心思想。6.什麼是遞歸什麼是迭代兩者的區別，舉例說明。7.回溯的含義是什麼舉例

1、貪心演算法主要是把問題分成很多局部問題，用局部最優解合成整體最優解。因此使用這種演算法需要此問題滿足兩個條件，一個是能夠分成多個能夠求解的局部問題，第二個就是局部問題的解能夠合成最優解。和動態規劃、回溯等相比差別就是再不回溯的前提下找出整體最優解或者接近最優解，速度快但應用有比較大的限制。

2、迭代也叫遞推，通過重復執行某一步驟或者函數來求得計算結果
遞歸是指函數中直接或者間接調用自身
舉例：
求a乘以2的10次方等於幾
迭代：
for (i=0;i<10;i++)
a *= 2;

遞歸：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}

db(a,0);

3、回溯的含義就是在搜索問題的狀態過程中，如果不能繼續前進，再向後回到岔口，換一條路繼續搜索，直到搜索完所有狀態或者查找到需要的狀態。
舉例：（最典型的就是樹的深度搜索，下面舉一個簡單的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//從3開始查找1
int read[10]=(0);//是否查找過
int readNum = 0;//查找過的個數
int forward = 1;//1為左，2為右
int tmp = 0,index = 5;

tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}

if (index <=0 || index>=9)
forward = 3 - forward;
}

⑨ 貪心思想

在學習數據結構的時候，我們已經見過了貪心思想在Prim和Kruskal中的完美應用，貪心思想因為其的簡潔在演算法中經常會被用到，有的時候在生活中，我們也會無意中使用到l貪心演算法。比如在去shopping時，經常需要進行找零錢的過程，我們總是不自覺的先把大的找出來。

那麼什麼是貪心思想？

貪心演算法總是作出在當前看來最好的選擇，也就是說貪心演算法並不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

只有在滿足最優子結構的情況下貪心演算法得到的結果才是最優結果。

比如找錢的問題，我要給你一百，那麼我盡可能每一次給你最多的。

或者比如磁碟的最優存儲問題，所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。

Prim和kruskal演算法都是每次選擇最小的邊納入生成樹。

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這也是貪心問題和動態規劃問題的主要區別。

在n行m列的正整數矩陣中，要求從每一行中選一個數，使得選出的n個數的和最大。

可運用貪心策略，選n次，每一次選相應行中的最大值即可。

但是，在一個n*m的方格陣中，每一格子賦予一個數，規定每次移動時只能向上或向右，現試找出一條路徑，使其從左下角至右上角所經過的權值之和最大。

同樣考慮貪心策略，從左下角向右上角移動，每次移動選擇權值較大的一個方向。

以2*3矩陣為例，採用貪心的策略得到的是1,3,4,6和為14但是實際的最優結果為1,2,100,6和為109.

所以說貪心演算法並不是總是可行，證明當前問題存在貪心選擇性質（全局最優解可以通過局部最優貪心選擇達到）和最優子結構性質（問題的最優解包含了其子問題的最優解）。所以貪心問題如果當前的選擇不會干擾之後的選擇，則不會出現問題。

其他的情況就需要進行證明，證明的最好辦法就是將最小子問題進行一步步的合並，直到最後還原為最後的原問題，若所得到的解是總體最優的則可以使用貪心思想，否則不可以。

比如上面的問題，我們的走一步的最優解為1，3，然後我們判斷一次走兩步的最優解是否任然為1,3這個路徑，答案顯然不是，變為 1,2,100這個路徑，所以顯然不能使用貪心思想。

假設1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張。現在要用這些錢來支付K元，至少要用多少張紙幣？用貪心演算法的思想，很顯然，每一步盡可能用面值大的紙幣即可。在日常生活中我們自然而然也是這么做的。

有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就占據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行。

部分背包問題， 有n個物體，第i個物體重量為wi,價值為vi,在總重量不超過C的情況下，讓總價值盡可能的高。每個物體都可以只取一部分。

我們可以考慮重量和價值的比值作為單價。

⑩ 電腦鼠兩種演算法法則

電腦鼠兩種演算法法則是貪心演算法和動態規劃演算法，具體如下：
1、貪心演算法：貪心演算法是一種簡單而常用的演算法，它的基本思想是在每一步選擇中都採取當前狀態下最優的選擇，以期望最終能夠達到全局最優。
2、動態規劃演算法：動態規劃演算法是一鎮察備種更加復雜和高效的演算法，它通過將問題拆分成若干個子沒殲問題，並且保御毀存子問題的解，從而避免了重復計算。