- 相關(guān)推薦
JAVA認(rèn)證基礎(chǔ)知識(shí)：近似算法（格雷厄姆算法）簡(jiǎn)介
之前做了很多貪心算法，他們都能找到最優(yōu)解，這也是之所以用貪心算法的原因。貪心算法較之其他，最大的優(yōu)勢(shì)體現(xiàn)在時(shí)間復(fù)雜度低，空間復(fù)雜度也比較低。對(duì)于試用貪心算法的題型，有兩個(gè)重要特征：貪心策略與最優(yōu)子結(jié)構(gòu)。貪心策略即每步采取策略的依據(jù);最優(yōu)子結(jié)構(gòu)則是指問題的求解可以轉(zhuǎn)化為求解子問題的最優(yōu)解。這點(diǎn)與動(dòng)態(tài)規(guī)劃有點(diǎn)像，但后者要枚舉問題的解空間，資源消耗很大。
貪心算法不一定保證得到最優(yōu)解，但很多時(shí)候用其他方法的無效(有的是確實(shí)沒有解決方法，有的是復(fù)雜度難以接受)，在這種情況下我們可以嘗試用近似算法，根據(jù)一定的有效貪心策略，哪怕得不到最優(yōu)解，但權(quán)衡之下也是可以接受的。
例如給定若干物品，要求盡可能的將它們分成質(zhì)量相近的兩堆。如物品數(shù)為5，重量分別為3,3,2,2,2，很容易根據(jù)經(jīng)驗(yàn)判斷分成3+3和 2+2+2的兩堆。但這是一個(gè)2^n級(jí)難題，數(shù)據(jù)量一大就出現(xiàn)組合爆炸。解決該問題目前還沒有無有效的方法。枚舉法可以得到最優(yōu)解，但時(shí)間復(fù)雜度為 O(2^n)，難以接受。下面是n<=15時(shí)的枚舉法，用位操作簡(jiǎn)化計(jì)算。
#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運(yùn)行結(jié)果為：2+2+2=6 3+3=6
格雷厄姆提出了解決該問題的近似算法。即每次從尚未分堆的物品中選擇最大我w[i]的，然后分別將它試探性加到已分的兩堆(a1,b1)中，若|a1+w[i]-b1|>|a1-w[i]-b1|,澤加到b1中;否則加到
a1中。已有神牛可以證明這樣的最終結(jié)果與最優(yōu)解的誤差不超過16%。下面是格雷厄姆算法的實(shí)現(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運(yùn)行結(jié)果為：2+2+3=7 2+3=7
在有些情況下是完全可以接受近似算法的。
【JAVA認(rèn)證基礎(chǔ)知識(shí)：近似算法格雷厄姆算法簡(jiǎn)介】相關(guān)文章：
SUN認(rèn)證JAVA程序員簡(jiǎn)介10-25
JAVA認(rèn)證基礎(chǔ)知識(shí)：JavaNativeInterface學(xué)習(xí)小結(jié)01-11
JAVA認(rèn)證基礎(chǔ)知識(shí)：基于反射機(jī)制的服務(wù)代理調(diào)用03-08
ACCP認(rèn)證簡(jiǎn)介11-10
思科認(rèn)證CCNA認(rèn)證考試簡(jiǎn)介06-08
SUN JAVA認(rèn)證介紹12-18
Java的基礎(chǔ)知識(shí)07-27