貪心演算法最優裝載

『壹』 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；

貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）

2. 對貪心法的深入理解

（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇

（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構

①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；

②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質

（3）解題關鍵：貪心策略的選擇

貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

（4）一般步驟：

①建立數學模型來描述最優化問題；

②把求解的最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解；

③證明做出貪心選擇後：

1°原問題總是存在全局最優解，即貪心選擇始終安全；

2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。

並完成2°

3. 貪心法與動態規劃

最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

『貳』 如何證明最優裝載問題具有貪心選擇性質

設某種貨幣系統為(1,5,10,25)四種幣值(單位:元)，要用最少的幣數找出 n元錢，
問:能否用貪心演算法進行求解，並證明。(不要求寫演算法) 參考解答:貪心性質(最大面額優先選最多)證明:
對 n<=25的情況，易由窮舉得證。
當 n>25時，設 n=1*a1+5*a2+10*a3+25*a4
為了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可將 5個 1元兌換為 1個 5元，幣數減少。
a2<2，若 a2>=2，可將 2個 5元兌換為 1個 10元，幣數減少。
當 a2=0時，a3<3，若 a3>=3，可將 3個 10元兌換為 1個 5元和 1個 25元，幣數減 少。
當 a2>0時，a3<2，若 a2>=2，可將 1個 5元和 2個 10元兌換為 1個 25元，幣數減 少。
即，為了使 a1+a2+a3+a4最小，所使用的 1、5、10元幣的幣數的上限為: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
則所使用的 1、5、10元幣的幣值上限為:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超過 25，因此，為了使 a1+a2+a3+a4最小，應使 a4達到最大。貪心選擇性質得 證。
最優子結構性質證明:
當 a4的值確定後，為了使 a1+a2+a3+a4達到最小，須使 a1+a2+a3達到最小，仍為同 型的最優問題。

『叄』 貪心演算法的最優裝載問題

void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)

1.void loading(int W[],int X[],int c,int n)
2.沒有定義i;
3.for（;;）是冒號，非逗號

『肆』 怎樣應用貪心演算法求得最優解

動態規劃要求。。具有最優子結構，記f[i]最優時，f[i - 1]的解也最優。。。最終可以得到最優解

貪心演算法，一般只能得到近優解或者局部最優解。。

『伍』 什麼是貪心演算法

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

『陸』 最優裝載：有一批集裝箱要裝上一艘載重量為totalW的輪船，其中集裝箱i的重量為wi。最有裝載問題要求在裝在

453453

『柒』 漫談演算法如何證明貪心演算法是最優 using exchange argument

這里主要是介紹一種證明貪心演算法是最優的一種方法：Exchange Argument （不知道應該怎麼翻譯到中文，交換參數？感覺聽起來挺別扭的，不像是一個方法的名字~o( □ )o）
Exchange Argument的主要的思想也就是 先假設 存在一個最優的演算法和我們的貪心演算法最接近，然後通過交換兩個演算法里的一個步驟(或元素)，得到一個新的最優的演算法，同時這個演算法比前一個最優演算法更接近於我們的貪心演算法，從而得到矛盾，原命題成立。
下面來看一個更為formal的解釋：
步驟：
Step0: 給出貪心演算法A的描述
Step1: 假設O是和A最相似(假設O和A的前k個步驟都相同，第k+1個開始不同，通常這個臨界的元素最重要)的最優演算法
Step2: [Key] 修改演算法O(用Exchange Argument，交換A和O中的一個元素)，得到新的演算法O』
Step3: 證明O』 是feasible的，也就是O』是對的
Step4: 證明O』至少和O一樣，即O』也是最優的
Step5: 得到矛盾，因為O』 比O 更和A 相似。
證畢。
當然上面的步驟還有一個變種，如下：
Step0: 給出貪心演算法A的描述
Step1: 假設O是一個最優演算法（隨便選，arbitrary）
Step2: 找出O和A中的一個不同。（當然這裡面的不同可以是一個元素在O不再A，或者是一個pair的順序在A的和在O的不一樣。這個要根據具體題目）
Step3：Exchange這個不同的東西，然後argue現在得到的演算法O 不必O差。
Step4: Argue 這樣的不同一共有Polynomial個，然後我exchange Polynomial次就可以消除所有的不同，同時保證了演算法的質量不比O差。這也就是說A 是as good as 一個O的。因為O是arbitrary選的，所以A是optimal的。
證畢
下面給幾個例子：
例 Maximum Cardinality Disjoint Interval Problem
問題描述：給一些時間片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一個元素個數最多的子集S，子集中的每個元素的時間片段沒有交叉。
Greedy Algorithm: 每次都選所有interval 中bi最小的那個，把（ai，bi）加入S，然後把（ai，bi）在T中刪除，同時把T中所有和（ai，bi）有交叉的interval刪除，然後再在T中找最小的bj，循環上面的操作，直到沒有可以在添加的。
證明上面說的Greedy Algorithm是最優的。
下面就用第一個證明的步驟來證。
我們的Greedy Algorithm記為A，假設A不是最優的，那麼就一定存在一個O，O是和A最相近的一個最優的演算法，最相近是指和O和A的前K-1個選擇都相同，第K個是不同的。
假設對於A，A第k個選擇的是（ai，bi）；而O第K個選擇的是（aj，bj）。從A的定義我們可以直到，bi<=bj。

『捌』 如何用貪心演算法解決磁碟文件最優存儲問題

dp??
方程為
a(fi,fj)=min{(a(fi,fk)+a(fk,fj)),a(fi,fj)}(k=i+1,i+2...j-1);

『玖』 為什麼貪心演算法可用於解決最優化問題

最優化問題是程序設計中一類非常重要的問題。每一個最優化問題都包含一組約束條件和一個優化函數，滿足約束條件的問題求解方案稱為問題的可行解，使優化函數取得最優值的可行解稱為問題的最優解。貪婪演算法是解決最優化問題的一種基本方法。
它採用逐步構造最優解的思想，在問題求解的每一個階段，都作出一個在一定標准下看上去最優的決策；決策一旦作出，就不可再更改。制定決策的依據稱為貪婪准則。