- 相關推薦
JAVA認證基礎知識：近似算法（格雷厄姆算法）簡介
之前做了很多貪心算法，他們都能找到最優解，這也是之所以用貪心算法的原因。貪心算法較之其他，最大的優勢體現在時間復雜度低，空間復雜度也比較低。對于試用貪心算法的題型，有兩個重要特征：貪心策略與最優子結構。貪心策略即每步采取策略的依據;最優子結構則是指問題的求解可以轉化為求解子問題的最優解。這點與動態規劃有點像，但后者要枚舉問題的解空間，資源消耗很大。
貪心算法不一定保證得到最優解，但很多時候用其他方法的無效(有的是確實沒有解決方法，有的是復雜度難以接受)，在這種情況下我們可以嘗試用近似算法，根據一定的有效貪心策略，哪怕得不到最優解，但權衡之下也是可以接受的。
例如給定若干物品，要求盡可能的將它們分成質量相近的兩堆。如物品數為5，重量分別為3,3,2,2,2，很容易根據經驗判斷分成3+3和 2+2+2的兩堆。但這是一個2^n級難題，數據量一大就出現組合爆炸。解決該問題目前還沒有無有效的方法。枚舉法可以得到最優解，但時間復雜度為 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運行結果為：2+2+2=6 3+3=6
格雷厄姆提出了解決該問題的近似算法。即每次從尚未分堆的物品中選擇最大我w[i]的，然后分別將它試探性加到已分的兩堆(a1,b1)中，若|a1+w[i]-b1|>|a1-w[i]-b1|,澤加到b1中;否則加到
a1中。已有神牛可以證明這樣的最終結果與最優解的誤差不超過16%。下面是格雷厄姆算法的實現。
#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認證基礎知識：近似算法格雷厄姆算法簡介】相關文章：
JAVA認證簡介03-19
JAVA認證基礎知識：JavaNativeInterface學習小結01-11
Adobe認證技能認證簡介03-19
Adobe認證ning認證簡介03-19