回溯算法

回溯法：也稱為試探法，它并不考慮問(wèn)題規(guī)模的大小，而是從問(wèn)題的最明顯的最小規(guī)模開始逐步求解出可能的答案，并以此慢慢地?cái)U(kuò)大問(wèn)題規(guī)模，迭代地逼近最終問(wèn)題的解。這種迭代類似于窮舉并且是試探性的，因?yàn)楫?dāng)目前的可能答案被測(cè)試出不可能可以獲得最終解時(shí)，則撤銷當(dāng)前的這一步求解過(guò)程，回溯到上一步尋找其他求解路徑。
為了能夠撤銷當(dāng)前的求解過(guò)程，必須保存上一步以來(lái)的求解路徑，這一點(diǎn)相當(dāng)重要。

• 八皇后問(wèn)題

8皇后問(wèn)題是其經(jīng)典的問(wèn)題,描述為:在一個(gè) 8x8的國(guó)際象棋棋盤中，怎樣放置8個(gè)皇后才能使8個(gè)皇 后之間不會(huì)互相有威脅而共同存在于棋局中，即在8x8個(gè)格子的棋盤中沒(méi)有任何兩個(gè)皇后是在同一行、同一列、同一斜線上。
思路:用回溯法,最容易想到的方法就是有序地從第 1 列的第 1 行開始，嘗試放上一個(gè)皇后，然后再嘗試第 2 列的第幾行能夠放上一個(gè)皇后，如果第 2 列也放置成功，那么就繼續(xù)放置第 3 列，如果此時(shí)第 3 列沒(méi)有一行可以放置一個(gè)皇后，說(shuō)明目前為止的嘗試是無(wú)效的（即不可能得到最終解），那么此時(shí)就應(yīng)該回溯到上一步（即第 2 步），將上一步（第 2 步）所放置的皇后的位置再重新取走放在另一個(gè)符合要求的地方…如此嘗試性地遍歷加上回溯，就可以慢慢地逼近最終解。
我們用代碼模擬該步驟,比較簡(jiǎn)單的是使用遞歸方法

 package com.fredal.structure;
public class NQueen {
   static int index=0;

   private static void show(int[] queen){
       for(int i=0;i<queen.length;i++){
           System.out.print(queen[i]+" ");
       }
       System.out.println();
       index++;
   }
   
   //k表示層數(shù) i表示列
   public static void process(int[] queen,int k){
       if(k==8){//找到解了
           show(queen);
           return;
       }
       for(int i=0;i<8;i++){
           
           if(!check(queen, k, i)) 
               continue;
           else {
               queen[k]=i;//放置皇后k
               process(queen, k+1);//放置皇后k+1
               queen[k]=-1;//更好地表示回溯 會(huì)被覆蓋的
           }
       }
   }
   
   //新皇后放入的位置
   private static boolean check(int[] queen,int row,int col){
       for(int i=0;i<row;i++) if(queen[i]==col) return false;//垂直檢測(cè)
       for(int i=0;i<row;i++) if(row-i==Math.abs(col-queen[i])) return false;//對(duì)角線檢測(cè)
       return true;
   }
   
   public static void main(String[] args) {
       int[] queen=new int[8];
       process(queen,0);
       System.out.println("共有"+index+"種解法");
   }
}

可以得到共有92種解法,我們注意到使用遞歸方法回溯的思想體現(xiàn)的不那么明顯,因?yàn)檫f歸是內(nèi)部自動(dòng)回溯的,效率也比非遞歸低一點(diǎn)的,所以我們又使用循環(huán)來(lái)模擬
關(guān)鍵在于如何回溯以及回溯的時(shí)機(jī),沖突了需要回溯,同時(shí)找到一個(gè)解之后仍然需要回溯,這點(diǎn)值得注意!

 package com.fredal.structure;
public class NQueen {
   static int index=0;
   private static void show(int[] queen){
       for(int i=0;i<queen.length;i++){
           System.out.print(queen[i]+" ");
       }
       System.out.println();
       index++;
   }    
   private static void init(int[] queen){
       for(int i=0;i<queen.length;i++){
           queen[i]=Integer.MAX_VALUE;
       }
   }
//k表示層數(shù),i表示列數(shù)
   public static void processS(int[] queen){
       int k=0,i=0;
       init(queen);//初始化數(shù)組
       while(k<8){
           while(i<8){
               if(check(queen, k, i)){
                   queen[k]=i;//放置皇后k
                   i=0;//探測(cè)下一行 將i清0 從下一行的第0列開始探測(cè)
                   break;
               }else{
                   ++i;//探測(cè)下一列
               }
           }
           
           if(queen[k]==Integer.MAX_VALUE){//第k行沒(méi)有找到可以放皇后的地方
               if(k==0) break;//回溯到第一行還沒(méi)有 就終止
               else{
                   --k;//回到上一行
                   i=queen[k]+1;//把上一行皇后的位置往后一列
                   queen[k]=Integer.MAX_VALUE;
                   continue;//清楚位置 重新探測(cè)
               }
           }
           
           if(k==7) {//找到解了
               show(queen);
               i=queen[k]+1;//把最后一行皇后的位置往后一列
               queen[k]=Integer.MAX_VALUE;
               continue;//清楚位置 重新探測(cè)
           }
           
           ++k;//探測(cè)下一行
       }
   }
   
   //新皇后放入的位置
   private static boolean check(int[] queen,int row,int col){
       for(int i=0;i<row;i++) if(queen[i]==col) return false;//垂直檢測(cè)
       for(int i=0;i<row;i++) if(row-i==Math.abs(col-queen[i])) return false;//對(duì)角線檢測(cè)
       return true;
   }
   
   public static void main(String[] args) {
       int[] queen=new int[8];
       processS(queen);
       System.out.println("共有"+index+"種解法");
   }
}

8皇后問(wèn)題擴(kuò)展到n皇后問(wèn)題是非常簡(jiǎn)單的,這兒就不做了.

• 迷宮問(wèn)題

迷宮問(wèn)題也是回溯法的經(jīng)典應(yīng)用,我們用代碼模擬過(guò)程

 package com.fredal.structure;
import java.util.HashSet;
import java.util.Set;
import com.fredal.structure.Maze.Position;
public class Maze {
   char maze[][];//存放迷宮
   Position entry;//入口
   Position exit;//出口
   Set<Position> res=new HashSet<Position>();//找到的解
   
   //位置類
   class Position{
       int row;
       int col;
       public Position(int row,int col){
           this.row=row;
           this.col=col;
       }
       public int hashCode() {
           return row*1000+col;
       }
       public boolean equals(Object obj) {
           if(obj instanceof Position==false) return false;
           Position p=(Position) obj;
           return p.row==row && p.col==col;
       }
       public String toString() {
           return "Position [row=" + row + ", col=" + col + "]";
       }
       
   }
   
   public Maze(){
       init();
   }
   
   //初始化迷宮
   private void init(){
       //硬編碼迷宮
       String[] x={
               "####A#######",
               "####....####",
               "####.####..#",
               "#....#####.#",
               "#.#####.##.#",
               "#.#####.##.#",
               "#.##.......#",
               "#.##.###.#.#",
               "#....###.#.#",
               "##.#.###.#.B",
               "##.###...###",
               "############"    
       };
       maze=new char[x.length][];
       for(int i=0;i<maze.length;i++){
           maze[i]=x[i].toCharArray();
           for(int j=0;j<maze[i].length;j++){
               if(maze[i][j]=='A') entry=new Position(i, j);
               if(maze[i][j]=='B') exit=new Position(i, j);
           }
       }
   }
   
   //核心程序
   private boolean findPath(Position cur,Set<Position> path){
       if(cur.equals(exit)) return true;//找到出口了
       path.add(cur);//path存放所有的路
       
       Position[] t={new Position(cur.row, cur.col-1),new Position(cur.row, cur.col+1),
               new Position(cur.row-1, cur.col),new Position(cur.row+1,cur.col)
       };//通過(guò)上下左右檢測(cè)
       
       for(int i=0;i<t.length;i++){
           try{
               if(maze[t[i].row][t[i].col]!='#' && path.contains(t[i])==false){//不是墻而且沒(méi)有訪問(wèn)過(guò)的
                   if(findPath(t[i], path)){//遞歸 自動(dòng)回溯
                       res.add(cur);//加入到結(jié)果中
                       return true;
                   }
               }
           }catch(Exception e){
               
           }
       }
       
       return false;
   }
   
   public void findPath(){
       Set path=new HashSet<Position>();//存放所有的路
       findPath(entry, path);
   }
   
   //打印迷宮
   public void show(){
       for(int i=0;i<maze.length;i++){
           for(int j=0;j<maze[i].length;j++){
               char c=maze[i][j];
               if(c=='.'&&res.contains(new Position(i, j))) c='o';//若被結(jié)果集包含就用圈表示
               System.out.print(c+" ");
           }
           System.out.println();
       }
   }
   
   public static void main(String[] args) {
       Maze m=new Maze();
       m.show();
       System.out.println();
       m.findPath();
       m.show();
   }
}

和8皇后問(wèn)題一樣,我們發(fā)現(xiàn)遞歸其實(shí)是內(nèi)部回溯,就是你在外面沒(méi)有自己去回溯,回溯思想沒(méi)有很好地體現(xiàn),還有效率問(wèn)題.
迷宮問(wèn)題我們可以采用棧來(lái)完美地模擬,并且很好地體現(xiàn)了回溯的思想,我對(duì)每一步都調(diào)用了show(),所以每一步的走法和如何回退都非常清晰.

 package com.fredal.structure;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;
import com.fredal.structure.Maze.Position;
public class MazeL {
       char maze[][];//存放迷宮
       Position entry;//入口
       Position exit;//出口
       Position cur;//當(dāng)前位置
       Stack<Position> res=new Stack<Position>();        
       //位置類
       class Position{
           int row;
           int col;
           public Position(int row,int col){
               this.row=row;
               this.col=col;
           }
           public int hashCode() {
               return row*1000+col;
           }
           public boolean equals(Object obj) {
               if(obj instanceof Position==false) return false;
               Position p=(Position) obj;
               return p.row==row && p.col==col;
           }
           public String toString() {
               return "Position [row=" + row + ", col=" + col + "]";
           }
           
       }    
       public MazeL(){
           init();
       }
       
       //初始化迷宮
       private void init(){
           //硬編碼迷宮
           String[] x={
                   "####A#######",
                   "####....####",
                   "####.####..#",
                   "#....#####.#",
                   "#.#####.##.#",
                   "#.#####.##.#",
                   "#.##.......#",
                   "#.##.###.#.#",
                   "#....###.#.#",
                   "##.#.###.#.B",
                   "##.###...###",
                   "############"    
           };
           maze=new char[x.length][];
           for(int i=0;i<maze.length;i++){
               maze[i]=x[i].toCharArray();
               for(int j=0;j<maze[i].length;j++){
                   if(maze[i][j]=='A') entry=new Position(i, j);
                   if(maze[i][j]=='B') exit=new Position(i, j);
               }
           }
           cur=entry;//初始化為起點(diǎn)
       }
       
       //核心程序
       public boolean findPath(){
           while(!cur.equals(exit)){
               //當(dāng)前位置入棧
               res.push(cur);
               maze[cur.row][cur.col]='x';//標(biāo)記為已經(jīng)過(guò)
               //開始上下左右搜索
               if(cur.col-1>0&&maze[cur.row][cur.col-1]!='#'&&maze[cur.row][cur.col-1]!='x'){
                   cur=new Position(cur.row, cur.col-1);
                   show();
               }
               else if(cur.col+1<12&&maze[cur.row][cur.col+1]!='#'&&maze[cur.row][cur.col+1]!='x'){
                   cur=new Position(cur.row, cur.col+1);
                   show();
               }
               else if(cur.row-1>0&&maze[cur.row-1][cur.col]!='#'&&maze[cur.row-1][cur.col]!='x'){
                   cur=new Position(cur.row-1, cur.col);
                   show();
               }
               else if(cur.row+1<12&&maze[cur.row+1][cur.col]!='#'&&maze[cur.row+1][cur.col]!='x'){
                   cur=new Position(cur.row+1, cur.col);
                   show();
               }
               else{//四條路都走不通
                   show();
                   if(!res.isEmpty()){
                       res.pop();//回溯
                       cur=res.peek();
                       res.pop();//彈兩次是因?yàn)橐婚_始還要push進(jìn)來(lái)
                   }
               }
           }            
           return false;
       }
       //打印迷宮
       public void show(){
           for(int i=0;i<maze.length;i++){
               for(int j=0;j<maze[i].length;j++){
                   char c=maze[i][j];
                   if(res.contains(new Position(i, j))) c='o';//若被結(jié)果集包含就用圈表示
                   if(c=='x') c='.';//把走過(guò)的那些岔路重新用.表示
                   System.out.print(c+" ");
               }
               System.out.println();
           }
           System.out.println();
       }
       
       public static void main(String[] args) {
           MazeL m=new MazeL();
           m.findPath();
           m.show();
       }
}

隨機(jī)化算法

隨機(jī)化算法,在算法中使用隨機(jī)函數(shù),其中決策依賴于某種隨機(jī)事件,基本特征是同一個(gè)實(shí)例用統(tǒng)一隨機(jī)化算法得到可能完全不同的結(jié)果.

• 隨機(jī)數(shù)生成器

首先當(dāng)然要產(chǎn)生隨機(jī)數(shù)啦.隨機(jī)數(shù)在概率算法中扮演著十分重要的角色,現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù),都是在一定程度上隨記的,即偽隨機(jī).
產(chǎn)生隨機(jī)數(shù)最常用的是線性同余法.數(shù)x1,x2,...的生成滿足:Xi+1=A Xi mod M.剛開始給出的值X0稱為種子.這里我們一般取M為31比特?cái)?shù)即2147483647,取A為48271這個(gè)素?cái)?shù).據(jù)此我們可以設(shè)計(jì)算法

  package com.fredal.structure;
public class Random {

   private static final int A=48271;
   private static final int M=Integer.MAX_VALUE;
   private static final int Q=(M/A);
   private static final int R= (M%A);
   
   private int state;
   
   public Random(){//使用系統(tǒng)時(shí)間與inf的余數(shù)作為種子
       state=(int) (System.currentTimeMillis()%Integer.MAX_VALUE);
   }
   
   public int RandomInt(){
       int tmpState=A*(state%Q)-R*(state/Q);
       if(tmpState>=0) state=tmpState;
       else state=tmpState+M;
       return state;
   }
   
   public double Random0_1(){//產(chǎn)生0-1之間的隨機(jī)數(shù)
       return (double)RandomInt()/M;
   }
   
   public static void main(String[] args) {
       Random m=new Random();
       for(int i=0;i<20;i++){
          System.out.println(m.Random0_1());
       }
   }
}

這里最關(guān)鍵的問(wèn)題在于Q和R是啥,還有RandomInt()的里面按照公式直接返回(A*state)%M不行么,嗯,這個(gè)問(wèn)題在于乘法可能溢出.解決溢出雖然可以使用64比特的long,但是減慢計(jì)算速度.
于是Schrage給出了算法,計(jì)算M/A的商和余數(shù)并分別定義為Q和R,那么按照程序中的算法,可以確保不溢出.推導(dǎo)可以查相關(guān)資料.
注: 接下去本節(jié)默認(rèn)使用上面實(shí)現(xiàn)的隨機(jī)數(shù)產(chǎn)生器

• 數(shù)值概率算法

顧名思義,這個(gè),就是最簡(jiǎn)單直接的隨機(jī)化算法.
比較有趣的例子是用概率模擬去求π的值,眾所周知,在邊長(zhǎng)為a的正方形內(nèi)部畫一個(gè)最大的四分之一圓,面積是πa2/4,那么與正方形面積之比是π/4,很容易算出π的值.
怎么算面積只比呢,那就是概率模擬咯

  package com.fredal.structure;
public class Pi {
   //假設(shè)邊長(zhǎng)為1的正方形
   public static double go(Random r,long n){
       long k=0;
       for(long i=0;i<n;i++){
           double x=r.Random0_1();
           double y=r.Random0_1();
           if(x*x+y*y<1) k++;//當(dāng)與原點(diǎn)距離小于1就認(rèn)為在四分之一圓內(nèi)
       }
       
       return 4*k/(double)n;
   }
   
   public static void main(String[] args) {
       Random r=new Random();
       System.out.println(go(r, 1000));
       System.out.println(go(r, 10000));
       System.out.println(go(r, 100000));
       System.out.println(go(r, 1000000));
       System.out.println(go(r, 10000000));
       System.out.println(go(r, 100000000));
   }
}

比較有趣的一點(diǎn)是,除了100次1000次這種實(shí)在不太靠譜之外,并不是次數(shù)越多就越精確的噢!!不相信可以多實(shí)驗(yàn)幾次.

• 舍伍德算法(Sherwood)

舍伍德算法的公式推導(dǎo),復(fù)雜度計(jì)算啥的可以參考維基百科,這里說(shuō)一下基本思想:在一般輸入數(shù)據(jù)的程序里，輸入多多少少會(huì)影響到算法的計(jì)算復(fù)雜度。這時(shí)可用舍伍德算法消除算法所需計(jì)算時(shí)間與輸入實(shí)例間的這種聯(lián)系.
舍伍德算法總能求得問(wèn)題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí)，可以在這個(gè)確定算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消除或減少問(wèn)題的好壞實(shí)例間的這種差別。舍伍德算法精髓不是避免算法的最壞情況行為，而是設(shè)法消除這種最壞行為與特定實(shí)例之間的關(guān)聯(lián)性。
它可以獲得很好的平均性能,很典型的例子就是之前我們說(shuō)的快速排序,參考快速排序.選取標(biāo)桿時(shí)第一種是無(wú)腦選取第一個(gè),還有是我們采用了三數(shù)中值法,當(dāng)然隨記選取標(biāo)桿也是很自然的想法.
這里現(xiàn)在上面寫的隨記類中加一個(gè)方法

  //0-n的隨記整數(shù)
   public int Random(int n){
       return (int) (Random0_1()*(n+1));
   }

可以開始寫了

  package com.fredal.structure;
public class Sherwood {
   
    public static void main(String[] args) {
       Random r=new Random();
       int[] a={14,7,2,34,6,95,27,9,54,12,103};
       quickSort(a, 0, a.length-1,r);
       for(int i=0;i<a.length;i++){
           System.out.print(a[i]+" ");
       }
   }

   public static void quickSort(int[] a,int left,int right,Random r){
       if(left<right){//遞歸出口條件
           if(left<right){//遞歸出口條件
               int i=left;//左指針
               int j=right;//右指針
               int random=left+r.Random(right-left);//隨機(jī)化選取標(biāo)桿
               System.out.println(random);
               int tmp=a[left];//交換
               a[left]=a[random];
               a[random]=tmp;
               
               int x=a[left];
               while(i<j){
                   while(i<j && a[j]>=x) j--;//從右向左找第一個(gè)小于x的數(shù)
                   if(i<j) a[i++]=a[j];
                   while(i<j && a[i]<x) i++;//從左向右找第一個(gè)大于等于x的數(shù)
                   if(i<j) a[j--]=a[i];
               } 
               a[i]=x;//插入標(biāo)尺
               quickSort(a,left,i-1,r);//遞歸左邊
               quickSort(a, i+1, right,r);//遞歸右邊
           }
       }
   }
}

當(dāng)然舍伍德算法有局限性,很多情況下所給的確定性算法無(wú)法直接改造成舍伍德算法,這時(shí)候可以借助隨機(jī)預(yù)處理技術(shù),僅對(duì)輸入進(jìn)行隨機(jī)洗牌,同樣可以達(dá)到舍伍德算法的效果.
還是就快速排序說(shuō),隨記選取標(biāo)桿確實(shí)是一個(gè)方法,但是在排序前對(duì)數(shù)組隨機(jī)洗牌一次,再選第一個(gè)作為標(biāo)桿,也是一樣的嘛..

  package com.fredal.structure;
import java.util.Arrays;
public class Sherwood {
   
    public static void main(String[] args) {
       Random r=new Random();
       int[] a={14,7,2,34,6,95,27,9,54,12,103};
       quickSort(a, 0, a.length-1,r);
       show(a);
   }
   
   //隨記洗牌算法
   public static void shuffle(int[] a,Random r){
       int len=a.length;
       for(int i=0;i<len;i++){
           int j=r.Random(len-1);
           if(i!=j){
               int tmp=a[i];
               a[i]=a[j];
               a[j]=tmp;
           }
       }
   }
   
   static void show(int[] a)
   {
       for(int i=0; i<a.length; i++) System.out.print(a[i] + " ");
       System.out.println();
   }

   public static void quickSort(int[] a,int left,int right,Random r){
       if(left<right){//遞歸出口條件
           if(left<right){//遞歸出口條件
               int i=left;//左指針
               int j=right;//右指針

               int[] shuffle=Arrays.copyOfRange(a, left, right);//注意不要把整個(gè)a拿來(lái)shuflle了~
               shuffle(shuffle, r);
               
               int x=a[left];
               while(i<j){
                   while(i<j && a[j]>=x) j--;//從右向左找第一個(gè)小于x的數(shù)
                   if(i<j) a[i++]=a[j];
                   while(i<j && a[i]<x) i++;//從左向右找第一個(gè)大于等于x的數(shù)
                   if(i<j) a[j--]=a[i];
               } 
               a[i]=x;//插入標(biāo)尺
               quickSort(a,left,i-1,r);//遞歸左邊
               quickSort(a, i+1, right,r);//遞歸右邊
           }
       }
   }
}

• 拉斯維加斯算法(Las Vegas)

同樣只說(shuō)一下基本思想:拉斯維加斯算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。但有時(shí)用拉斯維加斯算法找不到解.所以通常用一個(gè)布爾函數(shù)來(lái)表示

void Obstinate(InputType x, OutputType y){
   // 反復(fù)調(diào)用拉斯維加斯算法LV(x, y)，直到找到問(wèn)題的一個(gè)解
   boolean success= false;
   while (!success) 
        success = LV(x,y);
}

設(shè)p(x)是對(duì)輸入x調(diào)用拉斯維加斯算法獲得問(wèn)題的一個(gè)解的概率,t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需的平均時(shí)間,s(x)和e(x)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間.
容易得到:t(x)=p(x)s(x)+(1-p(x))(e(x)+tx(x)),可以解得t(x)=s(x)+((1-p(x))/p(x))e(x)
我們?cè)诨厮莘ǖ臅r(shí)候講過(guò)8皇后問(wèn)題,之前是從0往后遞增地放,并采用回溯.但其實(shí)每個(gè)皇后在棋盤山位置無(wú)規(guī)律,不具有系統(tǒng)性,用拉斯維加斯算法十分自然.
從第0行開始,每一行得皇后擺放的位置都是隨記的,如果擺放不了沖突了就全盤否定掉重新開始,而不是采用回溯往前退一步.由于我們是采用隨記的算法,所以仍然有較高的概率找到解的.
要講的是這兒設(shè)計(jì)算法注意的問(wèn)題.每一步放皇后的位置是隨機(jī)的,很容易想到這么寫:

 while(!check(queen,k,i)){
    i=r.Random(7);
 }

其實(shí)這么寫很容易理解,就是每一步檢驗(yàn)通不過(guò)的時(shí)候就一直采取新的隨機(jī)數(shù).
但是會(huì)有一個(gè)問(wèn)題,前幾行也許沒(méi)問(wèn)題,但是假如這一行沒(méi)有可以放的列,我們就一直死循環(huán)了,那怎么辦,設(shè)置循環(huán)多少次之后就默認(rèn)找不到了然后重新開始?
好吧剛開始確實(shí)掉死胡同里去,其實(shí)可以先遍歷一遍這一行的所有列,在那些可行的列里面再進(jìn)行隨記選取.

  package com.fredal.structure;
public class LVQueen {
   private static void show(int[] queen){
       for(int i=0;i<queen.length;i++){
           System.out.print(queen[i]+" ");
       }
       System.out.println();
   }
    static Random r=new Random();//隨機(jī)數(shù)產(chǎn)生器
   //拉斯維加斯算法
   public static boolean QueenLV(int[] queen){
       int k=0,i=0;//k表示行 i表示列
       int[] can = new int[8];//用來(lái)保存可以遍歷的那些列
       int count=1;
       while(k<8&&count>0){//每一層
           count=0;//置為0
           for(int j=0;j<8;j++){//遍歷所有列
               if(check(queen, k, j))
                   can[count++]=j;
           }
           if(count>0)//說(shuō)明可以找到存放的地方
               queen[k++]=can[r.Random(count-1)];//可能存放的列里面隨便選一個(gè)
       }
       return (count>0);
   }
   //測(cè)試新皇后放入的位置
   private static boolean check(int[] queen,int row,int col){
       for(int i=0;i<row;i++) if(queen[i]==col) return false;//垂直檢測(cè)
       for(int i=0;i<row;i++) if(row-i==Math.abs(col-queen[i])) return false;//對(duì)角線檢測(cè)
       return true;
   }
   public static void main(String[] args) {
       int[] queen=new int[8];
       while(!QueenLV(queen)){//如果找不到可以存放的位置的話就重新來(lái)過(guò)(count=0)
           
       }
       show(queen);
   }
}

有興趣的還可以測(cè)試一下成功率.當(dāng)然其實(shí)純粹采用拉斯維加斯算法也不是最好的,我們可以采取拉斯維加斯算法與回溯法相結(jié)合,即前幾行用隨機(jī)化,后幾行開始用回溯法.

  package com.fredal.structure;
public class LVQueen {
   private static void show(int[] queen){
       for(int i=0;i<queen.length;i++){            System.out.print(queen[i]+" ");
       }
       System.out.println();
   }
    static Random r=new Random();//隨機(jī)數(shù)產(chǎn)生器
   //拉斯維加斯算法
   public static boolean QueenLV(int[] queen,int stopVeags){
       int k=0,i=0;//k表示行 i表示列
       int[] can = new int[8];//用來(lái)保存可以遍歷的那些列
       int count=1;
       while(k<stopVeags&&count>0){//每一層
           count=0;//置為0
           for(int j=0;j<8;j++){//遍歷所有列
               if(check(queen, k, j))
                   can[count++]=j;
           }
           if(count>0)//說(shuō)明可以找到存放的地方
               queen[k++]=can[r.Random(count-1)];//可能存放的列里面隨便選一個(gè)
       }
       return (count>0);
   }
   
   //回溯法
   public static void BackTrack(int[] queen,int k){
       if(k==8){//找到解了
           show(queen);
           return;
       }
       for(int i=0;i<8;i++){            
           if(!check(queen, k, i)) 
               continue;
           else {
               queen[k]=i;//放置皇后k
               BackTrack(queen, k+1);//放置皇后k+1
               queen[k]=-1;//更好地表示回溯 會(huì)被覆蓋的
           }
       }
   }
   
   //測(cè)試新皇后放入的位置
   private static boolean check(int[] queen,int row,int col){
       for(int i=0;i<row;i++) if(queen[i]==col) return false;//垂直檢測(cè)
       for(int i=0;i<row;i++) if(row-i==Math.abs(col-queen[i])) return false;//對(duì)角線檢測(cè)
       return true;
   }
   
   //為了測(cè)試成功率方便 寫一個(gè)函數(shù)
   public static void nQueen(int[] queen,int stopVeags){//stopVeags表示前多少行用拉斯維加斯,后面的用回溯
       while(!QueenLV(queen, stopVeags)){
       }
       BackTrack(queen, stopVeags);
   }
   
   public static void main(String[] args) {
       int[] queen=new int[8];
       nQueen(queen, 2);//試試前面兩行隨機(jī)化,后面回溯
   }
}

有興趣地測(cè)試一下選取的stopVeags不同對(duì)成功率以及解的個(gè)數(shù)的影響,還有性能.籠統(tǒng)的說(shuō),當(dāng)stopVeags為1和8的時(shí)候成功率應(yīng)該是1,1的時(shí)候解有92個(gè),8的時(shí)候就是1個(gè).從2到7遞增的話成功率是遞減,解必然遞減.性能的話按照我之前測(cè)試貌似是取2的時(shí)候最好.
除了著名的8皇后問(wèn)題,來(lái)說(shuō)一下尋找第k小的數(shù)這個(gè)問(wèn)題,我們采用拉斯維加斯算法,很容易得到

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindTheKMin {    
   public static void main(String[] args) {
       Integer[] a={12,56,73,45,9,51,43,67,11};
       List<Integer> lst=Arrays.asList(a);
       while(!find(lst, 2)){        
       }
   }
   public static boolean find(List<Integer> a,int index){
       //Random r=new Random();//放到外面去...
       int random=(int)(Math.random()*a.size());
       int mid=a.get(random);//隨記選擇一個(gè)數(shù)
       List<Integer> s1=new ArrayList<Integer>();
       
       for(Integer x:a){//記錄比mid數(shù)小的
           if(x<mid)
               s1.add(x);
       }
       
       if(s1.size()==index-1){//比mid數(shù)小的數(shù)量等于index-1 說(shuō)明找到了
           System.out.println(mid);
           return true;
       }
       
       return false;
   }
}

這里有點(diǎn)小問(wèn)題,不知道為什么用我自己寫的隨機(jī)數(shù)產(chǎn)生器性能低得令人發(fā)指(好吧我知道了,我怎么把隨機(jī)數(shù)生成器放到方法里去了,隨機(jī)性沒(méi)了).但這個(gè)思路是沒(méi)錯(cuò)的,就是隨機(jī)選一個(gè),看看是不是符合要求,不符合重新來(lái)一遍...
當(dāng)然這個(gè)太暴力了,而且當(dāng)我們要求的數(shù)有很多重復(fù)值的時(shí)候,成功率降低很多,我們還是加點(diǎn)優(yōu)化,加點(diǎn)分治法之類的...

  package com.fredal.structure;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FindTheKMin {    
   public static void main(String[] args) {
       Integer[] a={12,56,73,45,9,51,43,67,11};
       List<Integer> lst=Arrays.asList(a);
       find(lst, 7);
   }
   static Random r=new Random();
   public static void find(List<Integer> a,int index){
       int random=r.Random(a.size()-1);
       int mid=a.get(random);//隨記選擇一個(gè)數(shù)
       List<Integer> s1=new ArrayList<Integer>();
       List<Integer> s2=new ArrayList<Integer>();
       List<Integer> s3=new ArrayList<Integer>();
       
       for(Integer x:a){//記錄比mid數(shù)小的,相等的,大的
           if(x<mid)
               s1.add(x);
           else if(x==mid)
               s2.add(x);//可能有重復(fù)值
           else if(x>mid)
               s3.add(x);
       }
       
       if(s1.size()>=index)
           find(s1,index);//說(shuō)明在s1內(nèi)
       else if(s1.size()+s2.size()>=index){
           System.out.println(mid);//說(shuō)明在s2內(nèi)
           return;
       }else if(s1.size()+s2.size()<index)
           find(s3, index-s1.size()-s2.size());//說(shuō)明在s3內(nèi)
   }
}

其實(shí)這個(gè)我認(rèn)為和拉斯維加斯算法差得有點(diǎn)遠(yuǎn)了,但是算法不用拘泥.當(dāng)然也可以用舍伍德隨即洗牌之類的算,每次先shuffle一下,一樣的.

• 蒙特卡洛算法(Monte Carlo)

首先要講一下,隨機(jī)化算法之間并不是涇渭分明的,像之前隨機(jī)投點(diǎn)法求π也算蒙特卡洛算法,只有蒙特卡洛算法與拉斯維加斯算法有著比較明顯的區(qū)別,前者是以高概率給出正確解,但無(wú)法確定那個(gè)是不是正確解.后者是給出的解一定是正確的,但可能給不出...夠明顯的區(qū)別了吧...
基本思想:當(dāng)所要求解的問(wèn)題是某種事件出現(xiàn)的概率，或者是某個(gè)隨機(jī)變量的期望值時(shí)，它們可以通過(guò)某種“試驗(yàn)”的方法，得到這種事件出現(xiàn)的頻率，或者這個(gè)隨機(jī)變數(shù)的平均值，并用它們作為問(wèn)題的解。
公式推導(dǎo)啥的維基百科去,直接上例子
主元素問(wèn)題:問(wèn)題描述標(biāo)準(zhǔn)版自行谷歌,由于沒(méi)弄好LaTeX,我感性地描述一下,就是一個(gè)元素要有很多重復(fù),而且重復(fù)的數(shù)量超過(guò)整個(gè)數(shù)組的一半了,他就是主元素...
編碼很簡(jiǎn)單:

  package com.fredal.structure;
public class Major {
   static Random r=new Random();
   private static boolean MajorMC(int[] a){        
       int random=r.Random(a.length-1);
       int x=a[random];//隨記選取元素
       int index=0;
       for(int i=0;i<a.length;i++){
           if(a[i]==x)
               index++;
       }
       if(index>(a.length/2)){
           System.out.println(x);//順便把主元素輸出了
           return (index>(a.length/2));//如果是主元素 概率大于1/2
       }
       return false;
   }
   
   public static boolean MajorMC(int[] a,double e){
       int k = (int) Math.ceil(Math.log(1.0/e) / Math.log(2.0));//e表示錯(cuò)誤的概率 
       for(int i=0;i<k;i++){
           if(MajorMC(a)) return true;//重復(fù)的調(diào)用MajorMC().有一次成功說(shuō)明有主函數(shù)
       }
       return false;
   }
   
   public static void main(String[] args) {
       int a[]={5,4,3,5,6,5,7,5,5,5,7,1,5,5};
           System.out.println(MajorMC(a, 0.001));
   }
}

思路很簡(jiǎn)單,就是隨機(jī)選取一個(gè)數(shù),如果有主元素的話,那么這個(gè)數(shù)不是主元素的概率小于1/2.至于重復(fù)選取多少次呢,我們程序中e為錯(cuò)誤的概率,那么顯然我們只調(diào)用一次的話,出錯(cuò)概率為0.5.想要降低到e的概率,那么應(yīng)該調(diào)用log(1/e)次算法(以2為底).可以自行推導(dǎo).
然后講一講素性測(cè)試,在前面,我們講過(guò)了篩法求素?cái)?shù),參考篩法求素?cái)?shù).
素性測(cè)試基于兩個(gè)定理:費(fèi)馬小定理,以及關(guān)于平方探測(cè)定理.
費(fèi)馬小定理:如果P是素?cái)?shù),且0<A<P,那么A^(P-1) mod P=1.證明不在這寫了,首先我們可以隨機(jī) 選取一個(gè)數(shù)A,如果A^(P-1) mod P=1的話,那么宣布P為素?cái)?shù),否則肯定不是素?cái)?shù).
嗯,有些數(shù)不是素?cái)?shù)但是它的大部分A的選擇都可以通過(guò)驗(yàn)證,這些數(shù)集叫Carmichael數(shù).最小的是561.
于是我們需要平方探測(cè)定理:如果P是素?cái)?shù)且0<X<P,那么X2 mod P=1僅有兩個(gè)解X=1,P=1.證明很 簡(jiǎn)單.
還是寫代碼吧,但是之前先考慮一個(gè)問(wèn)題,如何求a^(n-1)次方呢,用Math.power()么,這個(gè)是可以但是 我們所需的空間太龐大.這里我們有種巧妙的方法.
對(duì)于m=41=101001，b5b4b3b2b1b0=101001，可以這樣來(lái)求a^m：
初始C=1.
b5=1：C=C^2(=1)，∵b5=1->C=aC(=a);
b5b4=10：C=C^2(=a2)，∵b4=0，不做動(dòng)作；
b5b4b3=101：C=C^2(=a4)，∵b3=1，做C=aC(=a^5)；
b5b4b3b2=1010：C=C^2(=a10)，∵b2=0，不做動(dòng)作；
b5b4b3b2b1=10100：C=C^2(=a20)，∵b1=0，不做動(dòng)作；
b5b4b3b2b1b0=101001:C←C^2(=a40)，∵b0=1->C=a*C(=a^41)。
完了之后我們還要對(duì)a^(n-1)對(duì)n求模,那么顯然我們可以在每一步動(dòng)作后就求模,而不用等全部算完才求模.還有一點(diǎn),中間的算平方步驟可以完美地進(jìn)行平方探測(cè).一舉兩得.

   package com.fredal.structure;
   public class IsPrime {
   //計(jì)算a^i mod n  
    private static long witness( long a, long i, long n )
       {
           if( i == 0 )
               return 1; //二進(jìn)制最高位,開始回退

           long x = witness( a, i / 2, n );//遞歸調(diào)用            
           if( x == 0 ){//如果遞歸回來(lái)的是0 說(shuō)明之前平方探測(cè)失敗 直接返回就行了
               return 0;               
           }
           long y = ( x * x ) % n;//順帶平方探測(cè)!,注意是順帶,二進(jìn)制求次方的關(guān)鍵
           if( y == 1 && x != 1 && x != n - 1 )//表示平方探測(cè)失敗
               return 0;
           if( i % 2 != 0 )
               y = ( a * y ) % n;//二進(jìn)制如果是1 就再乘以一次a再取模
           return y;
       }
       static Random r = new Random( );
       public static boolean isPrime( long n )
       {
           for( int counter = 0; counter < 10; counter++ )//反復(fù)調(diào)用10次
               if( witness( r.randomLong( 2, n - 2 ), n - 1, n ) != 1 )
                   return false;
           return true;
       }
       public static void main( String [ ] args )
       {
          for(int i=500;i<600;i++){
              if(isPrime(i))
                  System.out.println(i);
          }
       }
}

動(dòng)態(tài)規(guī)劃(Dynamic Programming)

動(dòng)態(tài)規(guī)劃是通過(guò)拆分問(wèn)題，定義問(wèn)題狀態(tài)和狀態(tài)之間的關(guān)系，使得問(wèn)題能夠以遞推（或者說(shuō)分治）的?式去解決.
動(dòng)態(tài)規(guī)劃最重要的兩個(gè)要點(diǎn)：

1. 狀態(tài)(狀態(tài)不太好找,可先從轉(zhuǎn)化方程分析)
2. 狀態(tài)間的轉(zhuǎn)化方程(從問(wèn)題的隱含條件出發(fā)尋找遞推關(guān)系)

動(dòng)態(tài)規(guī)劃：適用于子問(wèn)題不是獨(dú)立的情況，也就是各子問(wèn)題包含公共的子子問(wèn)題，鑒于會(huì)重復(fù)的求解各子問(wèn)題，DP對(duì)每個(gè)問(wèn)題只求解一遍，將其保存在一張表中，從而避免重復(fù)計(jì)算.

• 自頂向下求最短路徑

1

 package com.fredal.structure;
import java.util.Arrays;
public class TopToBottom {
   public static int minimum(int[][] t){
       int n=t.length;
       int[][] result=new int[n][n];//存放結(jié)果
           
       result[0][0]=t[0][0];//初始化條件
       
       for(int i=1;i<n;i++){
           for(int j=0;j<=i;j++){
               if(j==0)
                   result[i][j]=result[i-1][j];//第一列時(shí)候 就等于本列上一行的結(jié)果
               if(j==i)
                   result[i][j]=result[i-1][j-1];//最后一列 等于前一列上一行的結(jié)果
               if(j>0 && j<i)
                   result[i][j]=min(result[i-1][j],result[i-1][j-1]);//取最小值
               result[i][j]+=t[i][j];//加上自身的數(shù)值
           }
       }
       
       int sum=Integer.MAX_VALUE;
       for(int i=0;i<n;i++){
           sum=min(sum, result[n-1][i]);//在最后一行取最小值
       }
       return sum;
   }
   private static int min(int i, int j) {
       return i<j?i:j;
   }    
   public static void main(String[] args) {
       int t[][]={
               {2},
               {3,4},
               {6,5,7},
               {4,1,8,3}
       }        System.out.println(minimum(t));
   }
}

接著是自底向上考慮,按照轉(zhuǎn)狀態(tài)移方程可得:

 package com.fredal.structure;
public class BottomToTop {
   public static int minimum(int[][] t){
       int n=t.length;
       int[][] result=new int[n][n];//存放結(jié)果
           
       for(int i=0;i<n;i++){//初始化條件
           result[n-1][i]=t[n-1][i];
       }
       
       for(int i=n-2;i>=0;i--){
           for(int j=0;j<=i;j++){
               result[i][j]=min(result[i+1][j], result[i+1][j+1])+t[i][j];//狀態(tài)轉(zhuǎn)移方程
           }
       }
       
       return result[0][0];//頂部就是最小值
   }

   private static int min(int i, int j) {
       return i<j?i:j;
   }
   
   public static void main(String[] args) {
       int t[][]={
               {2},
               {3,4},
               {6,5,7},
               {4,1,8,3}
       };        System.out.println(minimum(t));
   }
}

這種方式雖然思維逆向一點(diǎn),但編碼方便一點(diǎn).

• LCS(最長(zhǎng)公共子序列)

該問(wèn)題描述如下:一個(gè)數(shù)列 S，如果分別是兩個(gè)或多個(gè)已知數(shù)列的子序列，且是所有符合此條件序列中最長(zhǎng)的，則 S 稱為已知序列的最長(zhǎng)公共子序列。
例如：輸入兩個(gè)字符串 BDCABA 和ABCBDAB，字符串 BCBA 和 BDAB 都是是它們的最長(zhǎng)公共子序列，則輸出它們的長(zhǎng)度 4，并打印任意一個(gè)子序列.
稍加推理可以得出遞歸結(jié)構(gòu)的方程:

2

3

4

  package com.fredal.structure;
import java.util.LinkedList;
public class LCS {
   private static Character[] result;
   
   public static int[][] LCS(char[] X,char[] Y){
       int[][] c=new int[X.length+1][Y.length+1];//存放最長(zhǎng)子序列長(zhǎng)度,長(zhǎng)度加1是因?yàn)?第一行第一列拿來(lái)初始化了
       
       //第一行第一列 自動(dòng)初始化為0
       for(int i=1;i<=X.length;i++){
           for(int j=1;j<=Y.length;j++){
               if(X[i-1]==Y[j-1])
                   c[i][j]=c[i-1][j-1]+1;
               else if(c[i-1][j]>=c[i][j-1])
                   c[i][j]=c[i-1][j];
               else
                   c[i][j]=c[i][j-1];
           }
       }
       
       return c;
   }
   //打印最長(zhǎng)子序列 使用遞歸
   public static void print(int[][] c,char[] x,char[] y,int i,int j,int len){
       if(i==0||j==0){//找到解了 就進(jìn)行輸出
           for(int k=0;k<c[x.length][y.length];k++){//遍歷結(jié)果數(shù)組
               System.out.print(result[k]);
           }
           System.out.println();
           return;
       }
       //結(jié)果數(shù)組是空 就初始化
       if(result==null)
           result=new Character[c[x.length][y.length]];
       
       if(x[i-1]==y[j-1]){//斜著遞歸
           len--;
           result[len]=x[i-1];//倒序加入結(jié)果數(shù)組
           print(c, x, y, i-1, j-1,len);
       }
       else if(c[i-1][j]>c[i][j-1])
           print(c, x, y, i-1, j,len);
       else if(c[i-1][j]<c[i][j-1])
           print(c, x, y, i, j-1,len);
       else {//說(shuō)明橫著和豎著都行  那就依次遞歸            
           print(c, x, y, i, j-1,len);
           print(c, x, y, i-1,j,len);
       }
   }
   
   public static void main(String[] args) {
       char[] x ={'A','B','C','B','D','A','B'}; 
       char[] y ={'B','D','C','A','B','A'}; 
       int[][] c =LCS(x,y);
       
       int len=c[x.length][y.length];
       System.out.println("最長(zhǎng)子序列長(zhǎng)度:"+len);
       
       print(c, x, y, x.length, y.length,len);
   }
}

要注意的是存放長(zhǎng)度的數(shù)組應(yīng)為字符數(shù)組長(zhǎng)度加1,因?yàn)槎嘤嘁涣心脕?lái)初始化狀態(tài).還有打印所有結(jié)果的時(shí)候,本來(lái)想用鏈表存儲(chǔ)子序列,這樣push,pop比數(shù)組方便一點(diǎn),但是鏈表在各個(gè)遞歸之間會(huì)相互影響,用數(shù)組則不會(huì)出現(xiàn)這種問(wèn)題.

• 最大子段和

就是一段數(shù)字?jǐn)?shù)組,求出連續(xù)的和最大的字段.注意要連續(xù),設(shè)b[j]為子段和,a[j]為每個(gè)數(shù),那么很簡(jiǎn)單的得出狀態(tài)方程是
b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n
主要就看當(dāng)b[j-1]>0時(shí)b[j]=b[j-1]+a[j]，否則b[j]=a[j]

  package com.fredal.structure;
import java.util.LinkedList;
public class MaxSubSum {
   public static void maxSum(int[] a){
       int n=a.length;
       int sum=0,b=0;//初始化最大子段和為0
       LinkedList<Integer> start=new LinkedList<Integer>();
       int flag=0,end=0;//設(shè)置子段位置參數(shù)
       for(int i=0;i<n;i++){
           if(b>0)
               b+=a[i];
           else{
               b=a[i];
               start.push(i);//更新開始下標(biāo)
               flag=1;
           }
           System.out.println(b);
           if(b>sum){
               sum=b;//更新最大子段和
               end=i;
               flag=0;
           }
           if(flag==1)//如果更新了開始下標(biāo),但卻沒(méi)有改變sum值,說(shuō)明是錯(cuò)誤的更新
               start.pop();
       }
       System.out.println("最大子段和是:從"+(start.pop()+1)+"到"+(end+1)+",和為"+sum);
   }
   
   public static void main(String[] args) {
       int[] a={1,2,6,-7,-3,-4};
       maxSum(a);
   }
}

這問(wèn)題求子段和不難,求兩端坐標(biāo)想了好一會(huì)兒,要注意b=a[i]時(shí)候更新開始下標(biāo)有可能是錯(cuò)誤的!.

• LIS(最長(zhǎng)遞增子序列)

問(wèn)題描述：找出一個(gè)n個(gè)數(shù)的序列的最長(zhǎng)單調(diào)遞增子序列： 比如A = {5,6,7,1,2,8,3,4,5} 的LIS是1,2,3,4,5.
我不得不吐槽,我認(rèn)為很多書,網(wǎng)上的博客都存在錯(cuò)誤,而會(huì)對(duì)初學(xué)者造成誤導(dǎo).
首先LIS[i] 是以arr[i]為末尾的LIS序列的長(zhǎng)度(這個(gè)概念并不正確,只是為了解決問(wèn)題設(shè)置的一個(gè)量)
可以得到LiS[i]=max(1,max(LIS(j)+1));j<i,arr[j]<arr[i](很多博客連這兒都寫錯(cuò),直接寫成了LiS[i]=max(LIS(j))+1,醉了.回過(guò)頭來(lái)雖然這個(gè)狀態(tài)轉(zhuǎn)移方程對(duì)于解決問(wèn)題是對(duì)的,只是和上面的概念是有沖突的)
那么按照序列是5,6,7,1,2,8,3,4,5,根據(jù)狀態(tài)方程計(jì)算LIS[1...i]應(yīng)該為1,2,3,1,2,4,3,4,5.看到?jīng)_突的地方了么,按照概念到1為止即LIS[4]應(yīng)該為3,但是按照方程應(yīng)該為1,而且只有按照后者計(jì)算結(jié)果才是對(duì)的.不啰嗦了給代碼:

  package com.fredal.structure;
public class LIS {
   public static void LIS(int[] a){
       int[] result=new int[a.length];
       int maxlen=0;//LIS長(zhǎng)度
       for(int i=0;i<a.length;i++){
           result[i]=1;//找不到比自己小的就設(shè)為1
           for(int j=0;j<i;j++){
               if(a[i]>a[j] && result[i]<result[j]+1){
                   result[i]=result[j]+1;
               }
           }
           if(result[i]>maxlen)
               maxlen=result[i];
       }        
       System.out.println("最長(zhǎng)上升子序列長(zhǎng)度為:"+maxlen);
   }
   
   public static void main(String[] args) {
       int[] a={5,6,7,1,2,9,3,4,5};
       LIS(a);
   }
}

這個(gè)算法的復(fù)雜度是O(n2),也不方便給出LIS序列(可以設(shè)置前驅(qū)什么的),下面給出復(fù)雜度是O(n log n)的算法.
我們需要一個(gè)數(shù)組B[]來(lái)記錄LIS的長(zhǎng)度以及序列中最大的值.初始化B[0]為arr[0],接著如果arr數(shù)組中的數(shù)比B數(shù)組中最大的數(shù),即末尾數(shù)大的話就添加到后面,否則就在數(shù)組B中找一個(gè)剛好比自己大的數(shù)(用二分實(shí)現(xiàn)),取代它.B數(shù)組的長(zhǎng)度就是LIS的長(zhǎng)度,但注意B數(shù)組并不是LIS...

  package com.fredal.structure;
import java.util.Arrays;
public class LIS {
   public static void show(int[] a){
       for(int i=0;i<a.length;i++){
           System.out.print(a[i]+" ");
       }
       System.out.println();
   }
   
   public static int LCSS(int[] arr){
       int[] B=new int[arr.length];
       int blen=1;
       B[0]=arr[0];//初始化
       show(B);
       for(int i=1;i<arr.length;i++){
           if(arr[i]>B[blen-1]){
               System.out.println(arr[i]+"插入");
               B[blen++]=arr[i];//比B中最大的元素大 就接在后面
               show(B);
           }
           else{    
               System.out.println(arr[i]+"替換");
               B[binarySearch(B, arr[i],blen)]=arr[i];//找一個(gè)剛剛比其大的元素,取代他的位置
               show(B);
           }
       }
       return blen;
   }
   // 在數(shù)組中查找一個(gè)元素剛剛大于arr[i]
   // 返回這個(gè)元素的index
   public static int binarySearch(int []arr, int n,int blen){
       int begin=0;
       int end=blen-1;
       while(begin<=end){
           int mid = begin+(end-begin)/2;
           if(arr[mid]==n)
               return mid;
           else if(arr[mid]>n)
               end=mid-1;
           else
               begin=mid+1;
       }
       return begin;
   }    
   public static void main(String[] args) {
       int[] a={5,6,7,1,2,9,3,4,5};
       System.out.println("最長(zhǎng)上升子序列長(zhǎng)度為"+LCSS(a));
   }
}

為了理解方便,每一步驟都進(jìn)行輸出,結(jié)果如下:

5

• 01背包問(wèn)題

如果有4個(gè)物品[2, 3, 5, 7].如果背包的大小為11，可以選擇[2, 3, 5]裝入背包，最多可以裝滿10的空間.如果背包的大小為12，可以選擇[2, 3, 7]裝入背包，最多可以裝滿12的空間.已知背包空間,函數(shù)需要返回最多能裝滿的空間大小
這是個(gè)典型的01背包問(wèn)題,設(shè)F[i,v]表示前i件物品恰好放入容量為v的背包所獲得的最大價(jià)值,第i件物品大小為Ci,價(jià)值為Wi,則其狀態(tài)轉(zhuǎn)移方程為:
F[i,v]=max(F[i-1,v],F[i-1,v-Ci]+Wi
只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只和前i ? 1件物品相關(guān)的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i ? 1件物品放入容量為v的背包中”，價(jià)值為F[i ? 1, v]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i ? 1件物品放入剩下的容量為v ? Ci的背包中”，此時(shí)能獲得的最大價(jià)值就是F[i ? 1, v ? Ci]再加上通過(guò)放入第i件物品獲得的價(jià)值Wi。
而在此題中,物品的大小與價(jià)值相當(dāng)于是相等的.我們用代碼模擬該問(wèn)題:

  package com.fredal.structure;
public class BackPack {
   public static int backpack(int[] a,int v){
       final int M=v;//背包空間
       final int N=a.length;
       int[][] f=new int[N+1][M+1];
       
       for(int i=0;i<N;i++){
           for(int j=0;j<=M;j++){//遍歷所有小于背包空間的所有空間情況 
               if(a[i]>j)//即j-a[i]<0,放不下 選擇不放
                   f[i+1][j]=f[i][j];
               else
                   f[i+1][j]=Math.max(f[i][j], f[i][j-a[i]]+a[i]);//看看放和不放哪個(gè)更優(yōu)
           }
       }
       
       return f[N][M];
   }
   
   public static void main(String[] args) {
       int[] a={2,3,5,7};
       System.out.println(backpack(a, 11));
   }
}

仍然是四件物品,大小為[2, 3, 5, 7],它們的價(jià)值為[1, 5, 2, 4], 問(wèn)如果是空間為10的背包,怎么裝可以獲得最大的價(jià)值.
這道題和前面那道差不多,多就多在他們的價(jià)值不等于他們的大小了.也很簡(jiǎn)單

  package com.fredal.structure;
public class BackPack {
   public static int backpack2(int[] a,int[] w,int v){
       final int M=v;//背包空間
       final int N=a.length;
       int[][] f=new int[N+1][M+1];
       
       for(int i=0;i<N;i++){
           for(int j=0;j<=M;j++){//遍歷所有小于背包空間的所有空間情況 
               if(a[i]>j)//即j-a[i]<0,放不下 選擇不放
                   f[i+1][j]=f[i][j];
               else
                   f[i+1][j]=Math.max(f[i][j], f[i][j-a[i]]+w[i]);//看看放和不放哪個(gè)更優(yōu)
           }
       }
       
       return f[N][M];
   }    
   public static void main(String[] args) {
       int[] a={2,3,5,7};
       int[] w={1,5,2,4};
       System.out.println(backpack2(a,w,10));
   }
}

背包問(wèn)題還有特別多可以講,完全背包,多重背包...以后有時(shí)間肯定要再細(xì)致好好地寫一下算法.
更多內(nèi)容以及相關(guān)下載訪問(wèn)擴(kuò)展閱讀