貪心演算法分析

① 貪心演算法的例題分析

例題1、
[0-1背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目標函數：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
⑵每次挑選所佔重量最小的物品裝入是否能得到最優解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
⑴貪心策略：選取價值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
⑵貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略：選取單位重量價值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程序無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
【注意：如果物品可以分割為任意大小，那麼策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條優化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
W=40
物品：A B C
重量：25 20 15
價值：25 20 15
附：本題是個DP問題，用貪心法並不一定可以求得最優解，以後了解了動態規劃演算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心演算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
【初步設計】
首先這是一個搜索問題，運用深度優先搜索進行求解。演算法如下：
⒈ 輸入初始位置坐標x,y；
⒉ 步驟 c:
如果c> 64輸出一個解，返回上一步驟c--
（x,y) ← c
計算(x,y）的八個方位的子結點，選出那些可行的子結點
循環遍歷所有可行子結點，步驟c++重復2
顯然⑵是一個遞歸調用的過程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//輸出一個解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八個方位子結點ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//遞歸調用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8個方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{確定新坐標是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判斷是否走過}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐標}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{遞歸}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{讀入開始坐標}Readln(x1,y1）；{讀入結束坐標}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判斷是否越界}ElseFind(x,y);Writeln('Total:',total){打出總數}END.這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎麼才能快速地得到部分解呢？
【貪心演算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。

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

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

③ 貪心演算法 部分背包問題

[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30
分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ?
值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
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，則答案錯誤。

④ 找零錢問題的貪心演算法

問題描述：
當前有面值分別為2角5分，1角，5分，1分的硬幣，請給出找n分錢的最佳方案（要求找出的硬幣數目最少）
問題分析：
根據常識，我們到店裡買東西找錢時，老闆總是先給我們最大面值的，要是不夠再找面值小一點的，直到找滿為止。如果老闆都給你找分數的或者幾角的，那你肯定不幹，另外，他也可能沒有那麼多零碎的錢給你找。其實這就是一個典型的貪心選擇問題。
問題的演算法設計與實現：
先舉個例子，假如老闆要找給我99分錢，他有上面的面值分別為25，10，5，1的硬幣數，為了找給我最少的硬幣數，那麼他是不是該這樣找呢，先看看該找多少個25分的， 99／25＝3，好像是3個，要是4個的話，我們還得再給老闆一個1分的，我不幹，那麼老闆只能給我3個25分，由於還少給我24，所以還得給我2個10分的和4個1分。
具體實現
//找零錢演算法
//By falcon
//輸入：數組m，依次存放從大到小排列的面值數，n為需要找的錢數，單位全部為分
//輸出：數組num，對照數組m中的面值存放不同面值的硬幣的個數，即找錢方案

⑤ tsp問題的貪心演算法，分析時間復雜度，試分析是否存在o的有效演算法

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產

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

《演算法分析與設計》是一門理論與應用並重的專業課程。本課程以演算法設計策略為知識單元，系統介紹計算機演算法的設計方法和分析技巧。課程主要內容包括:第1章，演算法概述；第二章，遞歸和分治策略；第三章，動態規劃；第四章，貪婪演算法；第五章，回溯法；第六章，分枝定界法。通過介紹經典實用的演算法，使學生掌握演算法設計的基本方法。結合案例分析，讓學生深入了解演算法設計的技巧和分析演算法的能力。

⑦ 求一個演算法(貪心演算法)

貪心演算法

一、演算法思想

貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1. 不能保證求得的最後解是最佳的；
2. 不能用來求最大或最小解問題；
3. 只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

二、例題分析

1、[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30

分析：

目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)

（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔重量最小的物品裝入是否能得到最優解？
（3）每次選取單位重量價值最大的物品，成為解本題的策略。 ?

值得注意的是，貪心演算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的演算法。
貪心演算法還是很常見的演算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的演算法中。
一般來說，貪心演算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
（1）貪心策略：選取價值最大者。反例：
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，則答案錯誤。

所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。（因為這一類演算法普及性不高，而且技術含量是非常高的，需要通過一些反例確定隨機的對象是什麼，隨機程度如何，但也是不能保證完全正確，只能是極大的幾率正確）

================================
三個經典的貪心演算法

有人說貪心演算法是最簡單的演算法，原因很簡單：你我其實都很貪，根本不用學。有人說貪心演算法是最復雜的演算法，原因也很簡單：這世上貪的人太多了，那輪到你我的份？

不論難度如何，貪心演算法都是一個很重要的演算法，我在網上N多Online Judge中的題目中，總結了三類較為常見，也十分經典的貪心演算法，發布在這兒Just For Fun。

（註：由於沒有現成的名字可用，這三種類型貪心演算法的名字都是我自己取的，如果你聽著別扭，請見諒。）

No 1.線段覆蓋（linescover）

題目大意：

在一維空間中告訴你N條線段的起始坐標與終止坐標，要求求出這些線段一共覆蓋了多大的長度。

解題思路：

將線段按其坐標進行排序（排序的具體方法:按起始坐標排，起始坐標相同的按終止坐標排，都是小在前大在後）,使之依次遞增，並按順序分別編號為X(i),X(i).a代表其起始坐標，X(i).b代表其終止坐標。

然後按排好的順序依次處理：定義一個變數last記錄考慮到當前線段之時被線段覆蓋的最大的坐標值，再定義一個變數length記錄當前線段覆蓋的長度。對於後面的線段，我們把它看成由兩個部分組成，即把它分成last之前的線段和last之後的線段。（如果線段全部處在last之後，其last之前的部分不存在。）由於我們排過序，我們可以肯定當前考慮的線段X(i)其處在last之前的部分不會對length造成影響（因為X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所處位置肯定被線段X(i-1)覆蓋過），所以會對length產生影響的即是X(i)處在last之後的部分。

所以我們可以依次對每條線段做如下處理：（初始化length為零，last為負無窮）

length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a (X(i).a>last)

last=X(i).b;

最後length就為我們所需要的答案。

No 2.最優數對（bestpair）

題目大意：

按遞增的順序告訴你N個正整數和一個實數P，要求求出求出該數列中的比例最接近P的兩個數（保證絕對沒有兩個數使得其比值為P）。

解題思路：

定義兩個指針i和j，先初始化i=j=1，然後進行如下操作：

當code[j]/code[i]>p時，inc（j）；

當code[j]/code[i]<p時，inc（i）。

記錄其中產生的最優值即為答案。

No 3.連續數之和最大值（maxsum）

題目大意：

給出一個長度為N的數列（數列中至少有一個正數），要求求出其中的連續數之和的最大值。（也可以加入a和b來限制連續數的長度不小於a且不大於b）。

解題思路：

先說不加限制的那種，定義一個統計變數tot，然後用循環進行如下操作：inc（tot，item） 其中如果出現tot<0的情況，則將tot賦值為0。在循環過程之中tot出現的最大值即為答案。

如果加入了限制條件的話，問題就變得難一些了（這句真的不是廢話）。為此我們先定義數組sum[i]來表示code[1]到code[i]之和（這樣的話code[a]~code[b]的和我們就可以用sum[b]-sum[a-1]來表示了。）。

再維護一個數組hash[i]來表示滿足條件的sum[a-1]的下標，並使之按遞增順序排列，這樣當前以第i的數為終止的數列的最大值肯定就是sum[i]-sum[hash[1]]。

現在我們來討論hash數組之中的數據需要滿足的條件和如何維護的具體問題：

當考慮到以第i個數為結尾時，hash[i]所表示的下標需要滿足的第一個條件就是題目規定的長度限制，我們需要實時的加入滿足長度規定的下標，刪除不符合要求的下標。其次，與不加限制條件時相同，若sum[i]-sum[hash[1]]的值小於零，則清空數組hash。

維護時可以這樣，當考慮到第i個數時，我們就將下標i-a+1加入到hash中，因為hash中原來已經排好序，因此我們我們可以用插入排序來維護hash的遞增性，然後我們考察hash[1]，若hash[1]<i-b+1，則證明其已超出長度限制，我們就將其刪除，接著再考慮更新後的hash[1],如此重復直至找到一個滿足條件的hash[1]為止。

我們可以用鏈表來表示hash，這樣就可以減少數據加入和刪除時頻繁數據移動的時間消耗。

記錄下sum[i]-sum[hash[1]]的最大值即為答案。

⑧ 採用貪心演算法進行安排。對演算法的時間和空間復雜度進行分析

時間主要是 排序用時了，快速排序 一般是 o(n*logn)
空間 復雜度基本上是 0(1)

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

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

⑩ 分析用動態規劃和貪心演算法求解背包問題的差異

動態規劃本質是以空間換時間，算出了所有可行解的值域。

而貪心演算法，每次選則最優的，而結果未必最優。
舉個簡單例子。
背包能裝8kg,有3個物品，分別為3kg,4kg,5kg
動態規劃，是計算，3+4， 3+5，得出解，最大的是3+5=8kg
貪心演算法，是選擇，第一次選最大的：5kg<8kg，第二次選則剩下的最大的4kg，4+5>8,故而解為5kg。