貪婪式演算法
A. 貪婪法是一種什麼樣的演算法
貪婪法是一種不求最優,只求滿意的演算法。
B. 哪些常見演算法屬於貪婪演算法
顯然KMP和FLOYD演算法不是貪心演算法，FLOYD演算法是使用了類似於動態規劃的思想，而KMP演算法則是對串的前綴進行去處理得到所有可能出現匹配的位置從而減少不必要的位移。貪心演算法可能還有很多，但是一般能用到的可能只有這些。在確定一個問題是否能用貪心來解決的時候應該線能夠證明在這里使用貪心演算法的正確性（詳見演算法導論）
C. 貪婪法演算法，求找零的最優方案，即從面值最大的開始找零！面值為:100元，50元，10元，5元，1元，0.5,0.1
我幫你把代碼修改了一下
#include<stdio.h>#include<stdlib.h>
#defineMax8
voidexchange(double,int[]);
doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};
intmain(){
inti;
intstore[Max]={0};
doublemoney;
printf("Inputmoneythatyouwillexchange!:");
scanf("%lf",&money);
doublepremoney=money;
exchange(money,store);
printf("%f ",premoney);
for(i=0;i<Max;i++){
if(store[i]>0)
printf("%d:%f ",store[i],moneyValues[i]);
}
return1;
}voidexchange(doubleexmoney,intstore[]){
inti;
for(i=0;i<Max;i++){
if(exmoney>moneyValues[i])break;
}
while(exmoney>0&&i<Max){
if(exmoney>moneyValues[i]){
exmoney-=moneyValues[i];
store[i]++;
}elseif(exmoney<0.1&&exmoney>0.05){
store[Max-1]++;
break;
}
elsei++;
}
return;
}然後，我覺得有些地方你寫得啰嗦了，幫你簡化了一下
#include<stdio.h>#include<stdlib.h>
#defineMax8
voidexchange(double,int[]);
doublemoneyValues[Max]={100,50,20,10,5,1,0.5,0.1};
intmain(){
inti;
intstore[Max]={0};
doublemoney;
printf("Inputmoneythatyouwillexchange!:");
scanf("%lf",&money);exchange(money,store);
printf("%f
",money);
for(i=0;i<Max;i++){
if(store[i]>0)
printf("%d:%f ",store[i],moneyValues[i]);
}
return1;
}voidexchange(doublemoney,intstore[]){
inti=0;
while(money>0&&i<Max){
if(money>moneyValues[i]){
money-=moneyValues[i];
store[i]++;
}elseif(money<0.1&&money>0.05){
store[Max-1]++;
break;
}
elsei++;
}
return;
}
D. 程序設計一課中提到的貪婪法基本思想是什麼啊
貪婪法是一種不追求最優解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。
貪婪演算法的一般方法
1、問題描述
它有n個輸入，而它的解就由這n個輸入的某個子集組成，只是這個子集必須滿足某些事先給定的條件。
2、約束條件 那些必須滿足的條件稱為約束條件。
3、可行解 滿足約束條件的子集稱為該問題的可行解。
4、目標函數 事先給定的衡量可行解優劣的量度標准，通常以函數的形式給出，稱為目標函數。
5、最優解 使目標函數取極值（極大或極小）的可行解，稱為最優解。
6、子結構模式 貪心技術中，問題的最優一般是原輸入的子集，獲取最優子集的貪心方法為子結構模式
7、有序模式 通過計算已有的判定而得出的最優條件，可以為下一步的判定提供依據，這種形式的貪心演算法稱為有序模式。
8、貪婪演算法求解思想（分步處理）
�8�4 根據題意，選取一種量度標准；
�8�4 然後按這種量度標准對這n個輸入排序，並按序一次輸入一個量。
�8�4 如果這個輸入和當前已構成在這種量度意義下的部分最優解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。
這種能夠得到某種意義下的最優解的分級處理方法稱為貪心演算法。
E. 貪婪啟發式和貪婪演算法的區別是什麼
馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種演算法稱為為貪心演算法，也叫貪婪演算法或啟發式演算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個演算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。
貪心演算法當然也有正確的時候。求最小生成樹的Prim演算法和Kruskal演算法都是漂亮的貪心演算法。
貪心法的應用演算法有Dijkstra的單源最短路徑和Chvatal的貪心集合覆蓋啟發式
所以需要說明的是，貪心演算法可以與隨機化演算法一起使用，具體的例子就不再多舉了。其實很多的智能演算法（也叫啟發式演算法），本質上就是貪心演算法和隨機化演算法結合——這樣的演算法結果雖然也是局部最優解，但是比單純的貪心演算法更靠近了最優解。例如遺傳演算法，模擬退火演算法。
F. 什麼是貪婪演算法
是貪心演算法吧……
就是每次都取最優值。。。比如合並果子：
有n堆果子，每個果子都有一個重量，每次可以任意選擇2堆果子將其合並成一堆，花費是這兩堆果子的重量值之和，求最終合並成一堆的最小(最大)花費。
演算法就是，每次取重量最小(最大)的兩堆果子合並，直到還剩一堆。
G. 請問數錢的貪婪演算法怎樣確保得到最優解
貪婪演算法：總是作出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，它所做出的僅是在某種意義上的局部最優解。
（註：貪婪演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題它能產生整體最優解。但其解必然是最優解的很好近似解。
基本思路：——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；
基本要素：
1、 貪婪選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇，即貪婪選擇來達到。（與動態規劃的主要區別）
採用自頂向下，以迭代的方式作出相繼的貪婪選擇，每作一次貪婪選擇就將所求問題簡化為一個規模更小的子問題。
對於一個具體問題，要確定它是否具有貪婪選擇的性質，我們必須證明每一步所作的貪婪選擇最終導致問題的最優解。通常可以首先證明問題的一個整體最優解，是從貪婪選擇開始的，而且作了貪婪選擇後，原問題簡化為一個規模更小的類似子問題。然後，用數學歸納法證明，通過每一步作貪婪選擇，最終可得到問題的一個整體最優解。
2、最優子結構性質:包含子問題的最優解
1、 設有n個活動的安排，其中每個活動都要求使用同一資源，如演講會場，而在同一時間只允許一個活動使用這一資源。每個活動都有使用的起始時間和結束時間。問：如何安排可以使這間會場的使用率最高。
活動 起始時間 結束時間
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 10
8 8 11
9 8 12
10 2 13
11 12 14
演算法：一開始選擇活動1，然後依次檢查活動一i是否與當前已選擇的所有活動相容，若相容則活動加入到已選擇的活動集合中，否則不選擇活動i,而繼續檢查下一活動的相容性。即：活動i的開始時間不早於最近加入的活動j的結束時間。
Prodere plan;
Begin
n:=length[e];
a {1};
j:=1;
for i:=2 to n do
if s[i]>=f[j] then
begin a a∪{i};
j:=i;
end
end;
例1 [找零錢] 一個小孩買了價值少於1美元的糖，並將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所採用的貪婪准則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等於要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。
假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然後是5美分的，最後加入兩個1美分的硬幣。
貪婪演算法有種直覺的傾向，在找零錢時，直覺告訴我們應使找出的硬幣數目最少（至少是接近最少的數目）。可以證明採用上述貪婪演算法找零錢時所用的硬幣數目的確最少（見練習1）。
H. 貪心演算法的特性
貪婪演算法可解決的問題通常大部分都有如下的特性：
⑴隨著演算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
⑵有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
⑶還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。
⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑸最後，目標函數給出解的值。
⑹為了解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第一個解通常是最優的。