琥珀春秋

贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。解活动安排问题的贪心算法就是一个例子。下面我们着重讨论可以用贪心算法求解的问题的一般特征。

对于一个具体的问题，我们怎么知道是否可用贪心算法来解此问题，以及能否得到问题的一个最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中

我们看到它们一般具有两个重要的性质：贪心选择性质和最优子结构性质。

1．贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

对于一个具体问题，要确定它是否具有贪心选择性质，我们必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。通常可以用我们在证明活动安排问题的贪心选择性质时所采用的方法来证明。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

2．最优子结构性质

当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。在活动安排问题中，其最优子结构性质表现为：若a是对于正的活动安排问题包含活动1的一个最优解,则相容活动集合a’=a—{1}是对于e’={i∈e:s_i≥f₁}的活动安排问题的一个最优解。

3．贪心算法与动态规划算法的差异

贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是，对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法来求解?是不是能用动态规划算法求解的问题也能用贪心算法来求解?下面我们来研究两个经典的组合优化问题，并以此来说明贪心算法与动态规划算法的主要差别。

public class heapSort {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] test = {10,655,2,15,49,43,23,90,34,63,62};//test[0]记录数组内元素个数
HeapSort(test);
for(int i=1;i System.out.print(test[i]+" ");
}

}

public static int parent(int i){
return (int)Math.floor((double)i/2);
}
public static int left(int i){
return 2*i;
}
public static int right(int i){
return 2*i+1;
}

public static void max_heapify(int[] arr,int i){
int largest,tmp;
int l = left(i);
int r = right(i);
if(l<=(arr[0])&&arr[l]>arr[i]){
largest = l;
}else
largest = i ;
if(r< =(arr[0])&&arr[r]>arr[largest])
largest = r;
if(largest !=i){
tmp = arr[i];
arr[i]=arr[largest];
arr[largest]=tmp;
max_heapify(arr,largest);
}
}
public static void buildMaxHeap(int[] arr){
for(int i=(int)Math.floor(arr[0]/2);i>0;i–)
max_heapify(arr,i);
}
public static void HeapSort(int[] arr){
int tmp;
buildMaxHeap(arr);
for(int i=arr[0];i>1;i–)
{
tmp = arr[1];
arr[1]=arr[i];
arr[i]=tmp;
arr[0]-=1;
max_heapify(arr,1);
}
}

}

遵循分治法的三步骤：
Divide（分解）：将问题分解成为一系列的子问题
Conquer （解决）：递归的解决子问题，若子问题足够小，直接求解
Combine （合并）：将子问题的结果合并成为原问题的解

public class InsertSort {

public static void main(String[] args){
int[] test = {3,5,6,2,67,57,23,97,26};
recursiveInsertion(test,test.length);
for(int t :test){
System.out.print(t+” “);
}
}
public static void recursiveInsertion(int[] arr , int length){
if(length>1){
recursiveInsertion(arr,length-1);
merge(arr,length-1,length);
}

}
public static void merge(int[] arr ,int end, int n){
int tmp=arr[n-1];
int i;
for(i=end-1;i>=0&&arr[i]>tmp;i–){
arr[i+1]=arr[i];
}
arr[i+1] = tmp;
}
}

斐波那契数列是一个神奇的数列。有很多生物的构成都同斐波那契数列成正相关，同时黄金分割同斐波那契数列也存在关系。

下面我们先写成Fibonacci数列的递归定义：

F(0) = 0 ;

F(1) = 0;

F(n) = F(n-1)+F(n-2);

。

通过上述的递归公式，我们即可给出Fibonacci数列的递归实现方式，这个算法，我想都是作为大家认识递归的入门算法，所以不在详述，下面来分析一下这个算法的时间复杂度。

F(n)=F(n-1)+F(n-2)。

如果利用递归树的分析方法来分析这个算法的话。

F(n)

F(n-1)                   F(n-2)

F(n-2)       F(n-3)   F(n-3)         F(n-4)

……………………………………………………….

从这个递归树中发现每一层上n只是降低了1或者2，而数据规模却在增大。因此当数据规模至1时，可以发现运行的时间是指数级的。

通过Fibonacci和黄金分割的关系，亦可证明Fibonacci的时间复杂度是指数级的。

黄金分割 Φ=（1+√5）/2  与它的共轭Ô=(1-√5)/2.

有如下关系:

F(i) =  (Φˆi-Ôˆi)/√5     （公式1）

如果忽略负数部分 ，可以发现F(i)接近于F(i) =  (Φˆi)/√5。

因此可以说明F(i)是指数增长的。

因此当求第n个Fibonacci数时，利用递归的方法来求解，需要花费大量时间。

那么如何才能将指数级的时间复杂度进行降低，一种方法是利用Fibonacci和黄金分割的关系，即公式1 ，然而这个数学公式在计算机里是无法表示的，所以这只能成为一种理论上的解法，实际无法存在。

因此考虑另外一种解法：

通过利用二阶矩阵来解决这个问题。

{{F(n+1) , F(n) } { F(n) , F(n-1) }}={{1 , 1 }{ 1,  0 }}^n

利用这个关于矩阵的公式，同时利用分治法，将{{1 , 1 }{ 1,  0 }}^n分成2个{{1 , 1 }{ 1,  0 }}^（n/2），逐次分解至n=1 ，观察对应的递归树，可以看到时间复杂度为lg(n)的。比起指数级的有很大的改进。

复习组成原理到这一章节，突然想起当初利用数组和文件完成大数阶乘，给自己下个功课，毕业前（时间比较久远）完成利用BCD码实现大数的乘法。总体思路上，自己还是把握到了，就是不知道c语言是否可以实现这样的功能。听说8421BCD在会计事务中很常见，计算很方便，尝试一下。

在学习data structure的时候，我们总是能够发现有很多时候，用递归来实现，算法会变得异常简单，其实，能够用递归实现的算法，都能够用非递归来实现，原因是因为在支持递归的编译程序中，在执行时，都是在内存中开辟一段栈，在函数调用子函数，子函数返回函数的时候，存在着一个入栈和出栈的操作。对于递归，自然是函数调用函数的过程，因此，我们只要能够搞明白内存中的栈的进出，就能够自己利用栈来编写非递归的算法。

01背包问题-回溯法

#include <stdio .h>
#include <stdlib .h>
 
int n=5,c=10;
int value[5]={6,3,5,4,6};
int weight[5]={2,2,6,5,4};
int cv[5]={0,0,0,0,0};
int bv[5]={0,0,0,0,0};
int cw=0;
int curv = 0 ;
int bestv =0 ;
void output()
{
   int i =0;
   for(i; i<n ; i++)
     printf("%d ",bv[i]);
   printf("%d",bestv);     
}
 
void trackback(int i)
{
     int j;
    if(i>=n)
    {
         if(bestv<curv ) 
        {
            for(j=0;j<n;j++)
                bv[j] = cv[j]; 
            bestv = curv;
        } 
    }
    else
    {
         if(cw + weight[i]<=c)
         {
          cv[i] = 1; 
          cw +=weight[i];
          curv+= value[i];
          trackback(i+1);
          cw -=weight[i];
          curv-= value[i];
          }
          cv[i] =0;
          trackback(i+1);
 
    }
 
 
}
int main(int argc, char *argv[])
{
  trackback(0);
  output();
  system("PAUSE");	
  return 0;
}

对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能地高。 Read more »