JAVA认证基础知识：近似算法（格雷厄姆算法）简介

相关推荐

　　之前做了很多贪心算法，他们都能找到最优解，这也是之所以用贪心算法的原因。贪心算法较之其他，最大的优势体现在时间复杂度低，空间复杂度也比较低。对于试用贪心算法的题型，有两个重要特征：贪心策略与最优子结构。贪心策略即每步采取策略的依据;最优子结构则是指问题的求解可以转化为求解子问题的最优解。这点与动态规划有点像，但后者要枚举问题的解空间，资源消耗很大。

JAVA认证基础知识：近似算法（格雷厄姆算法）简介

　　贪心算法不一定保证得到最优解，但很多时候用其他方法的无效(有的是确实没有解决方法，有的是复杂度难以接受)，在这种情况下我们可以尝试用近似算法，根据一定的有效贪心策略，哪怕得不到最优解，但权衡之下也是可以接受的。

　　例如给定若干物品，要求尽可能的将它们分成质量相近的两堆。如物品数为5，重量分别为3,3,2,2,2，很容易根据经验判断分成3+3和 2+2+2的两堆。但这是一个2^n级难题，数据量一大就出现组合爆炸。解决该问题目前还没有无有效的方法。枚举法可以得到最优解，但时间复杂度为 O(2^n)，难以接受。下面是n<=15时的枚举法，用位操作简化计算。

　　#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];