JAVA認證基礎知識：近似算法（格雷厄姆算法）簡介

　　之前做了很多貪心算法，他們都能找到最優(yōu)解，這也是之所以用貪心算法的原因。貪心算法較之其他，最大的優(yōu)勢體現(xiàn)在時間復雜度低，空間復雜度也比較低。對于試用貪心算法的題型，有兩個重要特征：貪心策略與最優(yōu)子結(jié)構(gòu)。貪心策略即每步采取策略的依據(jù);最優(yōu)子結(jié)構(gòu)則是指問題的求解可以轉(zhuǎn)化為求解子問題的最優(yōu)解。這點與動態(tài)規(guī)劃有點像，但后者要枚舉問題的解空間，資源消耗很大。

　　貪心算法不一定保證得到最優(yōu)解，但很多時候用其他方法的無效(有的是確實沒有解決方法，有的是復雜度難以接受)，在這種情況下我們可以嘗試用近似算法，根據(jù)一定的有效貪心策略，哪怕得不到最優(yōu)解，但權(quán)衡之下也是可以接受的。

　　例如給定若干物品，要求盡可能的將它們分成質(zhì)量相近的兩堆。如物品數(shù)為5，重量分別為3,3,2,2,2，很容易根據(jù)經(jīng)驗判斷分成3+3和 2+2+2的兩堆。但這是一個2^n級難題，數(shù)據(jù)量一大就出現(xiàn)組合爆炸。解決該問題目前還沒有無有效的方法。枚舉法可以得到最優(yōu)解，但時間復雜度為 O(2^n)，難以接受。下面是n<=15時的枚舉法，用位操作簡化計算。

　　#include

　　#include

　　using namespace std;

　　const int MAXN=20;

　　int w[MAXN];

　　int used[MAXN];

　　const int INF=1<<30;

　　int n,id,sum;

　　int Solve()

　　{

　　int min,cnt=1

　　memset(used,0,sizeof(used));

　　for(int i=0;i>w[i];

　　int ans=Solve();

　　for(int i=0;i運行結(jié)果為：2+2+2=6 3+3=6

　　格雷厄姆提出了解決該問題的近似算法。即每次從尚未分堆的物品中選擇最大我w[i]的，然后分別將它試探性加到已分的兩堆(a1,b1)中，若|a1+w[i]-b1|>|a1-w[i]-b1|,澤加到b1中;否則加到

　　a1中。已有神�？梢宰C明這樣的最終結(jié)果與最優(yōu)解的誤差不超過16%。下面是格雷厄姆算法的實現(xiàn)。

　　#include

　　#include

　　#include

　　using namespace std;

　　const int MAXN=20;

　　int w[MAXN];

　　int used[MAXN];

　　int n,a,b;

　　void Solve()

　　{

　　sort(w,w+n);

　　a=0,b=0;

　　for(int i=n-1;i>=0;i--)

　　{

　　if(abs(a+w[i]-b)<=abs(a-w[i]-b))

　　{

　　a+=w[i];

　　used[i]=true;

　　}

　　else b+=w[i];

　　}

　　}

　　int main()

　　{

　　cin>>n;

　　memset(used,0,sizeof(used));

　　for(int i=0;i>w[i];

　　Solve();

　　printf(" 第一堆為:");

　　for(int i=0;i運行結(jié)果為：2+2+3=7 2+3=7

　　在有些情況下是完全可以接受近似算法的。

【JAVA認證基礎知識：近似算法格雷厄姆算法簡介】相關(guān)文章：

Adobe認證ning認證簡介09-20

JAVA認證基礎知識：基于反射機制的服務代理調(diào)用07-18

NIIT認證簡介08-15

Oracle認證簡介08-05

微軟認證考試簡介09-23

思科認證體系簡介06-10

Sun java認證考試答案10-23

java認證考試培訓內(nèi)容08-21

JAVA考試認證經(jīng)驗分享09-20

蘇州紅帽認證工程師認證簡介07-13