❶ C語言程序問題——活動安排問題
題目出得不嚴密，題目要求是「計算安排的活動最多時會場使用時間」，但當「安排的活動最多」有多種安排方式，題目中卻沒說輸出這多種方式中的哪一種的會場使用時間。例如 ：當有3項活動要安排，開始時間和結束時間分別是1 2、3 5、4 5，這時可以安排第一項和第二項活動，也可以安排第一項和第三項活動，前者的會場使用時間是5，後者是4，這時是輸出4還是5，題目中沒用指出。先假設測試數據不會出現上述情況，則利用貪心演算法求解活動安排問題是一種最常用的方法：#include<stdio.h>
#include<stdlib.h>
struct activity
{
int start;
int end;
}act[8501];
int comp(const void *p, const void *q)
{
struct activity *a=(struct activity *)p;
struct activity *b=(struct activity *)q;
return a->end-b->end;
}
int main()
{
int i,k,res,e;
while(scanf("%d",&k)!=EOF)
{
for(i=0;i<k;i++) scanf("%d%d",&act[i].start,&act[i].end);
qsort(act,k,sizeof(act[0]),comp);
res=act[0].end-act[0].start+1;
e=act[0].end;
for(i=1;i<k;i++)
{
if(act[i].start>e)
{
res+=act[i].end-act[i].start+1;
e=act[i].end;
}
}
printf("%d\n",res);
}
return 0;
}
❷ 哈夫曼編碼（貪心演算法）
參考： 哈夫曼編碼
哈夫曼編碼是一種十分有效的編碼方法，廣泛應用於 數據壓縮 中
通過採用 不等長 的編碼方式，根據 字元頻率的不同 ，選擇 不同長度的編碼 ，對頻率 越高 的字元採用 越短 的編碼實現數據的高度壓縮。
這種對頻率越高的字元採用越短的編碼來編碼的方式應用的就是貪心演算法的思想。
下面看一個例子：
假如我們有一個包含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』』也應該符合條件，即貪婪演算法，每次取最小的兩個節點出來這種做法是正確的
❸ 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的情況下，讓總價值盡可能的高。每個物體都可以只取一部分。
我們可以考慮重量和價值的比值作為單價。
❺ 一道數學建模題
我有一個貪心演算法，就是說由於不論加班與否都是P1產品的利潤高，因此為了滿足利潤應該盡量在非加班時間生產P1產品，如此一來，P2產品的利潤應該是>=7*75=525，剩下的利潤還有3500-525=2975
如果A,B組都在非加班時間生產A產品，則可生產10*8+8*8=144kg，利潤為144*20=2880，還差95的利潤，即95/15=6或7kg，由於B的生產能力是8kg/h，所以7/8>7/10，所以由B生產8千克，此時P1的生產任務完成
再看P2，有75千克的生產任務，此時A組剩下4小時，B組3小時，摺合一共生產47kg，不達生產要求
此演算法應該是考慮到利潤最大化，而又盡量滿足生產任務的，因此應該沒有無法分配滿足題目要求的工作計劃
僅供參考
❻ (三) 貪心演算法
貪心演算法的思想非常簡單且演算法效率很高，在一些問題的解決上有著明顯的優勢。
假設有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就提出了一個有名的演算法。在每個結點對其子結點進行選取時，優先選擇『出口』最小的進行搜索，『出口』的意思是在這些子結點中它們的可行子結點的個數，也就是『孫子』結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現『死』結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜索純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。
❼ 貪心演算法及其應用
求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。
比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝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]，期望值就是盡可能多的區間。
我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。
貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。
❽ 高分懸賞貪心演算法的作業
一、演算法思想
貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
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）每次選取單位容量價值最大的物品，成為解本題的策略。 ?
2、[單源最短路徑]一個有向圖G，它的每條邊都有一個非負的權值c[i,j]，「路徑長度」就是所經過的所有邊的權值之和。對於源點需要找出從源點出發到達其他所有結點的最短路徑。
E.Dijkstra發明的貪婪演算法可以解決最短路徑問題。演算法的主要思想是：分步求出最短路徑，每一步產生一個到達新目的頂點的最短路徑。下一步所能達到的目的頂點通過如下貪婪准則選取：在未產生最短路徑的頂點中，選擇路徑最短的目的頂點。
設置頂點集合S並不斷作貪心選擇來擴充這個集合。當且僅當頂點到該頂點的最短路徑已知時該頂點屬於集合S。初始時S中只含源。
設u為G中一頂點，我們把從源點到u且中間僅經過集合S中的頂點的路稱為從源到u特殊路徑，並把這個特殊路徑記錄下來（例如程序中的dist[i，j]）。
每次從V-S選出具有最短特殊路徑長度的頂點u，將u添加到S中，同時對特殊路徑長度進行必要的修改。一旦V=S，就得到從源到其他所有頂點的最短路徑，也就得到問題的解 。
stra.pas
3、[機器調度]現有N項任務和無限多台機器。任務可以在機器上處理。每件任務開始時間和完成時間有下表：
任務 a b c d e f g
開始(si) 0 3 4 9 7 1 6
完成(fi) 2 7 7 11 10 5 8
在可行分配中每台機器在任何時刻最多處理一個任務。最優分配是指使用的機器最少的可行分配方案。請就本題給出的條件，求出最優分配。
?三、練習題：
已知5個城市之間有班機傳遞郵件，目的是為了尋找一條耗油量較少的飛行路線。5個城市的聯系網路如圖所示。圖中編號的結點表示城市，兩個城市之間的連線上的值表示班機沿該航線已行的耗油量，並假定從城市i到j和城市j到i之間的耗油量是相同的。
分析：
1. 運用貪心思想：
在每一步前進的選擇上，選取相對當前城市耗油量最小的航線；
2. 圖解：若從1出發，有圖：
總耗油量=14 1-2-5-3-4-1
但若路線改為：1-5-3-4-2-1，則總耗油量=13
所以，這樣的貪心法並不能得出最佳解。
3. 改善方案：
從所有城市出發的信心過程，求最優的。
編程：
1. 數據結構：
城市聯系網路圖的描述(圖的鄰接矩陣的描述)：
const
c=array[1..5,1..5] of integer=((0,1,2,7,5),
(1,0,4,4,3),
(2,4,0,1,2),
(7,4,1,0,3));
2. 貪心過程：
begin
初始化所有城市的算途徑標志；
設置出發城市V；
for i:=1 to n-1 do {n-1個城市}
begin
s:=從V至所有未曾到過的城市的邊集中耗油量最少的那個城市；
累加耗油量；
V:=s；
設V城市的訪問標志；
end;
最後一個城市返回第一個城市，累加耗油量；
end;
3. 主過程：實現改善方案
begin
for i:=1 to n do
begin
cost1:=maxint; {初始化}
調用貪心過程，返回本次搜索耗油量cost；
if cost<cost1 then 替換；
end;
輸出；
end
❾ 最佳調度問題（c/c++）
如果各機器運行速度相等，換句話就是任務無論在哪台機器上運行完成時間都相等，則問題較簡單
1 . 先將任務由大到小排序
2 . 計算n個任務需要的總時間和平均到k個機器上的時間
3 . 將大於平均時間的任務各分配一個機器，找到最大完成時間
4 . 將其他任務順序安排在一台機器上，如果時間超出最大時間，則把該任務交給下一個機器，下一個任務繼續在這台機器上試安排，直到所有任務都不能在小於最大完成時間的情況下安排
5 . 安排下一台機器直道所有任務安排完，
6 . 或有可能安排某(些)任務找不到小於最大完成時間 那麼重新掃描各台機器使再加上該任務後時間最小，按此方法安排萬所有任物
數據結構採用鏈表比較合適，
K個機器k個鏈，n個任務按大小順序插入一個鏈表，安排後從任務鏈表中移動到機器鏈表中。知道鏈表為空
❿ 程序員演算法基礎——貪心演算法
貪心是人類自帶的能力，貪心演算法是在貪心決策上進行統籌規劃的統稱。
比如一道常見的演算法筆試題---- 跳一跳 ：
我們自然而然能產生一種解法：盡可能的往右跳，看最後是否能到達。
本文即是對這種貪心決策的介紹。
狹義的貪心演算法指的是解最優化問題的一種特殊方法，解決過程中總是做出當下最好的選擇，因為具有最優子結構的特點，局部最優解可以得到全局最優解；這種貪心演算法是動態規劃的一種特例。 能用貪心解決的問題，也可以用動態規劃解決。
而廣義的貪心指的是一種通用的貪心策略，基於當前局面而進行貪心決策。以 跳一跳 的題目為例：
我們發現的題目的核心在於 向右能到達的最遠距離 ，我們用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]的值。
貪心的學習過程，就是對自己的思考進行優化。
是把握已有信息，進行最優化決策。
這里還有一些收集的 貪心練習題 ，可以實踐練習。
這里 還有在線分享，歡迎報名。