貪心科技演算法課

㈠ 數據結構之貪心演算法

貪婪演算法（Greedy）的定義：是一種在每一步選中都採取在當前狀態下最好或最優的選擇，從而希望導致結果是全局最好或最優的演算法。
貪婪演算法：當下做局部最優判斷，不能回退
（能回退的是回溯，最優+回退是動態規劃）
由於貪心演算法的高效性以及所求得答案比較接近最優結果，貪心演算法可以作為輔助演算法或解決一些要求
結果不特別精確的問題
注意：當下是最優的，並不一定全局是最優的。舉例如下：

有硬幣分值為10、9、4若干枚，問如果組成分值18，最少需要多少枚硬幣？
採用貪心演算法，選擇當下硬幣分值最大的：10
18-10=8
8/4=2
即：1個10、2個4，共需要3枚硬幣
實際上我們知道，選擇分值為9的硬幣，2枚就夠了
18/9=2
如果改成：

背包問題是演算法的經典問題，分為部分背包和0-1背包，主要區別如下：
部分背包：某件物品是一堆，可以帶走其一部分
0-1背包：對於某件物品，要麼被帶走（選擇了它），要麼不被帶走（沒有選擇它），不存在只帶走一部分的情況。
部分背包問題可以用貪心演算法求解，且能夠得到最優解。
假設一共有N件物品，第 i 件物品的價值為 Vi ，重量為Wi，一個小偷有一個最多隻能裝下重量為W的背包，他希望帶走的物品越有價值越好，可以帶走某件物品的一部分，請問：他應該選擇哪些物品？
假設背包可容納50Kg的重量，物品信息如下表：

將物品按單位重量 所具有的價值排序。總是優先選擇單位重量下價值最大的物品
按照我們的貪心策略，單位重量的價值排序： 物品A > 物品B > 物品C
因此，我們盡可能地多拿物品A，直到將物品1拿完之後，才去拿物品B，然後是物品C 可以只拿一部分.....

在不考慮排序的前提下，貪心演算法只需要一次循環，所以時間復雜度是O(n)

優點：性能高，能用貪心演算法解決的往往是最優解
缺點：在實際情況下能用的不多，用貪心演算法解的往往不是最好的

針對一組數據，我們定義了限制值和期望值，希望從中選出幾個數據，在滿足限制值的情況下，期望值最大。
每次選擇當前情況下，在對限制值同等貢獻量的情況下，對期望值貢獻最大的數據（局部最優而全局最優）
大部分能用貪心演算法解決的問題，貪心演算法的正確性都是顯而易見的，也不需要嚴格的數學推導證明
在實際情況下，用貪心演算法解決問題的思路，並不總能給出最優解

㈡ 貪心演算法及其應用

求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。

比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？

我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？

把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。

貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。

雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；

然而，實際上的最短路徑是S->B->D->T，總代價為6。

所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。

除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。

我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？

這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。

我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？

這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。

對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？

我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。

我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。

貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。

㈢ 貪心演算法總結 Greedy Algorithms

反證法：亂正
假設貪心不是最優解：

先考慮如何排序

Exchange argument:通過交換元素將最優解轉換為貪心解，但還保持最優性

當cache中不存在所需元素時，需要訪問cache交換元素。
目標：cache misses的次數最少

最優演算法：cache miss時替換當前future queries中最遠訪問的元素。
e.g. future queries中第一個元素g出現cache miss, 需要exchange，判斷current cache中需要替換哪個元素。
在future queries中

思路：構造最優規劃 ，它有最小的cache misses次數；Farthest-In-Future規劃 ,兩者在前 個請求的序列是相同的，如果能證明在第 步時， 可以轉化為 並且沒有增加cache misses的次數，則可以說明 是最優解。
最開始，假設 和 中元素如下：

Case 1: 元素已經在Cache中
假設下一個請求的元素是d顯然兩者都不會發生cache miss，故兩者總的cache misses次數還是相同；

Case 2: 元素不在Cache中， 和 與外界嘩李悔交換相同的元素
假設下一個請求的元素是e,兩者都用a與其交換，有

和 都增加了一次擾扒cache misses，故總cache misses次數還是相同；
Case 3: 元素不在Cache中， 和 與外界交換不同的元素
假設下一個請求的元素是e, 交換a, 交換b,有

之後，下一個請求的元素有四種情況：
Case 3a: 元素在 中, 不在 中; S交換a
也就是請求b,這時S用a交換b,有

有兩次cache misses，而 只有一次，之後 和 序列又保持一致；
Case 3b: 元素在 中, 不在 中; S不交換a
也就是請求b，S用c交換b，有

用a交換c，有

兩者cache misses次數相同，之後 和 序列又保持一致
Case 3c: 元素在 中, 不在 中
即請求a，這種情況不可能發生，因為S_{FF}移出的是最遠需要的元素，即request中a會排在b之後；
Case 3d: 元素不在 和 中
假設請求f, 用a交換f, 用b交換f,有

兩者cache misses次數相同，之後 和 序列又保持一致
的cache misses次數不會多於最優解 , 即 是最優解。

Single-link k-clustering 演算法：

㈣ 什麼是貪心演算法，用實例分析貪心演算法是如何解決實際問題

比如： int a=3,b=4,c; c=a+++b; 將被解釋為 c=(a++)+b; 而不會被解釋為 c=a+(++b); 貪心演算法的主要意義是從左至右依次解釋最多的符號！

㈤ 大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系

對於，大學課程《演算法分析與設計》中動態規劃和貪心演算法的區別和聯系這個問題，首先要來聊聊他們的聯系：1、都是一種推導演算法；2、將它們分解為子問題求解，它們都需要有最優子結構。這兩個特徵師門的聯系。

拓展資料：

貪婪演算法是指在解決問題時，它總是在當前做出最佳選擇。也就是說，在不考慮全局優化的情況下，該演算法在某種意義上獲得了局部最優解。貪婪演算法不能得到所有問題的全局最優解。關鍵是貪婪策略的選擇。

動態規劃是運籌學的一個分支，是解決決策過程優化的過程。20世紀50年代初，美國數學家R·貝爾曼等人在研究多階段決策過程的最優化問題時，提出了著名的最優化原理，建立了動態規劃。動態規劃在工程技術、經濟、工業生產、軍事和自動控制等領域有著廣泛的應用，在背包問題、生產經營問題、資金管理問題、資源分配問題、最短路徑問題和復雜系統可靠性問題上都取得了顯著的成果。

㈥ 貪心演算法的基本思路

1.建立數學模型來描述問題
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解，得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步
do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解。
下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。

㈦ 程序員演算法基礎——貪心演算法

貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。

比如一道常見的演算法筆試題---- 跳一跳 ：

我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。

狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。

而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用maxRight來表示；
此時有一種貪心的策略：從第1個盒子開始向右遍歷，對於每個經過的盒子，不斷更新maxRight的值。

貪心的思考過程類似動態規劃，依舊是兩步： 大事化小 ， 小事化了 。
大事化小：
一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題；
小事化了：
從小問題找到決策的核心，確定一種得到最優解的策略，比如跳一跳中的 向右能到達的最遠距離 ；

在證明局部的最優解是否可以推出全局最優解的時候，常會用到數學的證明方式。

如果是動態規劃：
要湊出m元，必須先湊出m-1、m-2、m-5、m-10元，我們用dp[i]表示湊出i元的最少紙幣數；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根據以上遞推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不對？ 平時我們找零錢有這么復雜嗎？
從貪心演算法角度出發，當m>10且我們有10元紙幣，我們優先使用10元紙幣，然後再是5元、2元、1元紙幣。
從日常生活的經驗知道，這么做是正確的，但是為什麼？

假如我們把題目變成這樣，原來的策略還能生效嗎？

接下來我們來分析這種策略：
已知對於m元紙幣，1，2，5元紙幣使用了a，b，c張，我們有a+2b+5c=m；
假設存在一種情況，1、2、5元紙幣使用數是x，y，z張，使用了更少的5元紙幣（z<c），且紙幣張數更少（x+y+z<a+b+c），即是用更少5元紙幣得到最優解。
我們令k=5*(c-z)，k元紙幣需要floor(k/2)張2元紙幣，k%2張1元紙幣；（因為如果有2張1元紙幣，可以使用1張2元紙幣來替代，故而1元紙幣只能是0張或者1張）
容易知道，減少(c-z)張5元紙幣，需要增加floor(5*(c-z)/2)張2元紙幣和(5*(c-z))%2張紙幣，而這使得x+y+z必然大於a+b+c。
由此我們知道不可能存在使用更少5元紙幣的更優解。
所以優先使用大額紙幣是一種正確的貪心選擇。

對於1、5、7元紙幣，比如說要湊出10元，如果優先使用7元紙幣，則張數是4；（1+1+1+7）
但如果只使用5元紙幣，則張數是2；（5+5）
在這種情況下，優先使用大額紙幣是不正確的貪心選擇。（但用動態規劃仍能得到最優解）

如果是動態規劃：
前i秒的完成的任務數，可以由前面1~i-1秒的任務完成數推過來。
我們用 dp[i]表示前i秒能完成的任務數 ；
在計算前i秒能完成的任務數時，對於第j個任務，我們有兩種決策：
1、不執行這個任務，那麼dp[i]沒有變化；
2、執行這個任務，那麼必須騰出來(Sj, Tj)這段時間，那麼 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如說對於任務j如果是第5秒開始第10秒結束，如果i>=10，那麼有 dp[i]=max(dp[i], dp[5] + 1)； （相當於把第5秒到第i秒的時間分配給任務j）

再考慮貪心的策略，現實生活中人們是如何安排這種多任務的事情？我換一種描述方式：

我們自然而然會想到一個策略： 先把結束時間早的兼職給做了！
為什麼？
因為先做完這個結束時間早的，能留出更多的時間做其他兼職。
我們天生具備了這種優化決策的能力。

這是一道 LeetCode題目 。
這個題目不能直接用動態規劃去解，比如用dp[i]表示前i個人需要的最少糖果數。
因為（前i個人的最少糖果數）這種狀態表示會收到第i+1個人的影響，如果a[i]>a[i+1]，那麼第i個人應該比第i+1個人多。
即是 這種狀態表示不具備無後效性。

如果是我們分配糖果，我們應該怎麼分配？
答案是： 從分數最低的開始。
按照分數排序，從最低開始分，每次判斷是否比左右的分數高。
假設每個人分c[i]個糖果，那麼對於第i個人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默認為0，如果在計算i的時候,c[i-1]為0，表示i-1的分數比i高）
但是，這樣解決的時間復雜度為 O(NLogN) ，主要瓶頸是在排序。
如果提交，會得到 Time Limit Exceeded 的提示。

我們需要對貪心的策略進行優化：
我們把左右兩種情況分開看。
如果只考慮比左邊的人分數高時，容易得到策略：
從左到右遍歷，如果a[i]>a[i-1]，則有c[i]=c[i-1]+1；否則c[i]=1。

再考慮比右邊的人分數高時，此時我們要從數組的最右邊，向左開始遍歷：
如果a[i]>a[i+1], 則有c[i]=c[i+1]+1；否則c[i]不變；

這樣講過兩次遍歷，我們可以得到一個分配方案，並且時間復雜度是 O(N) 。

題目給出關鍵信息：1、兩個人過河，耗時為較長的時間；
還有隱藏的信息：2、兩個人過河後，需要有一個人把船開回去；
要保證總時間盡可能小，這里有兩個關鍵原則： 應該使得兩個人時間差盡可能小（減少浪費），同時船回去的時間也盡可能小（減少等待）。

先不考慮空船回來的情況，如果有無限多的船，那麼應該怎麼分配？
答案： 每次從剩下的人選擇耗時最長的人，再選擇與他耗時最接近的人。

再考慮只有一條船的情況，假設有A/B/C三個人，並且耗時A<B<C。
那麼最快的方案是：A+B去, A回；A+C去；總耗時是A+B+C。（因為A是最快的，讓其他人來回時間只會更長， 減少等待的原則 ）

如果有A/B/C/D四個人，且耗時A<B<C<D，這時有兩種方案：
1、最快的來回送人方式，A+B去；A回；A+C去，A回；A+D去； 總耗時是B+C+D+2A （減少等待原則）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；總耗時是 3B+D+A （減少浪費原則）
對比方案1、2的選擇，我們發現差別僅在A+C和2B；
為何方案1、2差別里沒有D？
因為D最終一定要過河，且耗時一定為D。

如果有A/B/C/D/E 5個人，且耗時A<B<C<D<E，這時如何抉擇？
仍是從最慢的E看。（參考我們無限多船的情況）
方案1，減少等待；先送E過去，然後接著考慮四個人的情況；
方案2，減少浪費；先送E/D過去，然後接著考慮A/B/C三個人的情況；（4人的時候的方案2）

到5個人的時候，我們已經明顯發了一個特點：問題是重復，且可以由子問題去解決。
根據5個人的情況，我們可以推出狀態轉移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根據我們考慮的1、2、3、4個人的情況，我們分別可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的狀態轉移方程和初始化值，我們可以推出dp[n]的值。

貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。

㈧ 演算法分析與設計這門課程第四章貪心演算法的知識點有哪些

演算法分析與設計這門課第四章貪心演算法的知識點包含章節導引,第一節活動安排問題,第二節貪心演算法基本要素,第三節最優裝載,第四節單源最短路徑,第五節多機調度問題,課後練習,。