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