『壹』 什麼是 貪心演算法
貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解
『貳』 可用動態規劃演算法或貪心演算法求解的關鍵特徵是問題具有什麼性質
實際工程中動態規劃往往很難實現，但是求解能得到全局最優。
但是貪心演算法雖然較易陷入局部最優，但是求解效率極高。
若是決策量前後之間影響不是很大，且較大規模問題貪心法較好。
『叄』 貪心演算法的證明過程，是不是只有先證明了貪心選擇性質之後，再以貪心選擇為前提證明其最優子結構
對於一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。
證明的大致過程為：首先考察問題的一個整體最優解，並證明可修改這個最優解，使其以貪心選擇開始。做了貪心選擇後，原問題簡化為規模更小的類似子問題。然後用數學歸納法證明通過每一步做貪心選擇，最終可得到問題的整體最優解。其中，證明貪心選擇後的問題簡化為規模更小的類似子問題的關鍵在於利用該問題的最優子結構性質。
『肆』 貪心演算法的特性
貪婪演算法可解決的問題通常大部分都有如下的特性：
⑴隨著演算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
⑵有一個函數來檢查一個候選對象的集合是否提供了問題的解答。該函數不考慮此時的解決方法是否最優。
⑶還有一個函數檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數一樣，此時不考慮解決方法的最優性。
⑷選擇函數可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑸最後，目標函數給出解的值。
⑹為了解決問題，需要尋找一個構成解的候選對象集合，它可以優化目標函數，貪婪演算法一步一步的進行。起初，演算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函數，演算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那麼該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪演算法正確工作，那麼找到的第一個解通常是最優的。
『伍』 貪心演算法中，通常會讓證明貪心選擇性，請問，證明貪心選擇性的實質是什麼怎樣說明一個問題具有貪心選擇呢
一般都是要最省事的比如
設有n中不同面值的硬幣，個硬幣的面值春雨數組T[1：n]中，現在要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存於數組Coins[1:n]中。
對任意簽署0<=m<=20001，設計一個用最少硬幣找錢m的方法。
用貪心演算法，先用最大面值的，直到超出之前再改用更小面值的，超出之前再用更更小面值的。。直到正好。這樣最少
程序實例
#include<stdio.h>
void main()
{
int m;
int i;
printf("please input m:");
scanf("%d",&m);
int T[6] ={100,50,20,10,5,1};
int coins[6] = {0};
for(i = 0; i < 6; )
{
if(m < T[i])
{
i++;
continue;
}
while(m >= T[i])
{
m -= T[i];
coins[i]++;
}
i++;
}
for(i = 0; i < 6; i++)
if(coins==0)
printf("%-4d有 %-2d張\n",T[i],coins[i]);
printf("\n");
}
『陸』 計算機演算法設計與分析 簡述什麼是貪心選擇性質
貪心選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇來得到.
就是說,你需要證明當前問題可以通過選擇最好的那個元素（比如01背包,總能夠通過選擇當前重量最小的物品來得到最優解）來解決問題
證明：（每一步所做的貪心選擇最終導致問題的整體最優解）
//基本思路：考察一個問題的最優解,證明可修改該最優解,使得其從貪心選擇開始,然後用數學歸納法證明每一步都可以通過貪心選擇得到最優解
1,假定首選元素不是貪心選擇所要的元素,證明將首元素替換成貪心選擇所需元素,依然得到最優解；
2,數學歸納法證明每一步均可通過貪心選擇得到最優解
『柒』 演算法分析與設計什麼是貪心選擇性質
貪心選擇性質：所求問題的整體最優解可以通過一系列局部最優的選擇來得到.
就是說,你需要證明當前問題可以通過選擇最好的那個元素（比如01背包,總能夠通過選擇當前重量最小的物品來得到最優解）來解決問題
證明：（每一步所做的貪心選擇最終導致問題的整體最優解）
//基本思路：考察一個問題的最優解,證明可修改該最優解,使得其從貪心選擇開始,然後用數學歸納法證明每一步都可以通過貪心選擇得到最優解
1,假定首選元素不是貪心選擇所要的元素,證明將首元素替換成貪心選擇所需元素,依然得到最優解；
2,數學歸納法證明每一步均可通過貪心選擇得到最優解
請採納！
『捌』 貪心演算法的本質
1. 貪心法（Greedy Algorithm）定義
求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；
貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）
2. 對貪心法的深入理解
（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇
（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構
①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；
②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質
（3）解題關鍵：貪心策略的選擇
貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。
（4）一般步驟：
①建立數學模型來描述最優化問題；
②把求解的最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解；
③證明做出貪心選擇後：
1°原問題總是存在全局最優解，即貪心選擇始終安全；
2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。
並完成2°
3. 貪心法與動態規劃
最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。
『玖』 貪心演算法，這個貪心到底是什麼意思
貪心指目光短淺，只看到當前這一步的最優決策，而不考慮以後的決策。這樣的演算法只在特定的問題下是正確的。