引言：這道題目老師強(qiáng)調(diào)了肯定要考旅东，所以只有硬著頭皮將其復(fù)習(xí)了;下面是自己學(xué)習(xí)回溯算法的學(xué)習(xí)，僅供參考；
一：基本概念：
回溯算法：“回朔法”有通用的解題方法之稱瞬场。使用它可以系統(tǒng)搜索一個(gè)問題的所有解或者一個(gè)解〗Ы迹回溯法是一個(gè)即帶有系統(tǒng)性有帶有跳躍性的算法贯被。它在問題的解空間樹中，按照深度優(yōu)先的策略妆艘，從根節(jié)點(diǎn)出發(fā)搜索解空間樹彤灶。算法搜索到解空間的任意一點(diǎn)時(shí)先判斷該點(diǎn)是否包含問題的解，如果肯定不包含批旺，就跳過對(duì)以該節(jié)點(diǎn)為根的子樹的搜索幌陕，逐層向其祖先節(jié)點(diǎn)回溯。否則汽煮，進(jìn)入該子樹搏熄，繼續(xù)按照深度優(yōu)先策略搜索∠境啵回朔法求問題心例，要回溯到根，并且根節(jié)點(diǎn)的所有子樹都要遍歷完才結(jié)束翎卓∑跹回溯法求解問題時(shí)，只要求得一個(gè)解就可以結(jié)束失暴，這種以深度優(yōu)先方式系統(tǒng)的搜索問題解的方法稱之為回朔法坯门；

適用于：組合數(shù)較大的問題！

使用回朔法求解時(shí)逗扒，有兩種方法可以避免無效搜索:

1：使用約束函數(shù)在擴(kuò)展節(jié)點(diǎn)處剪去不滿足約束的子樹

2：使用限界函數(shù)剪去得不到最優(yōu)解的子樹古戴；

子集樹：當(dāng)所給的問題從n個(gè)元素的集合S中找出滿足某種性質(zhì)的子集時(shí)，相應(yīng)的解空間樹稱為子集樹矩肩。

排序樹：當(dāng)所給的問題是確定n個(gè)元素滿足某種性質(zhì)的排列時(shí)现恼，相應(yīng)的解空間樹稱之為排列樹。排序樹通常有n！葉結(jié)點(diǎn)叉袍。

使用回溯法求解問題通常包含以下3個(gè)步驟：

1：針對(duì)所給問題始锚，定義問題的解空間

2：確定易于搜索的解空間的結(jié)構(gòu)

3：以深度優(yōu)先的方式搜索解空間，并在搜索的過程中用剪支函數(shù)避免無效搜索喳逛；
二：?jiǎn)栴}描述：
現(xiàn)在有一個(gè)載重為10kg的背包瞧捌，共有5件物品可以裝載，他們的重量以及各個(gè)物品對(duì)應(yīng)的價(jià)值如下：
重量：{3.4kg,2.5kg,6kg,4kg,9.0kg};
價(jià)值：{3,2.5,5,9,6.2};
問怎么樣裝載這些物品使得最終所得的價(jià)值最大润文？
求解步驟：
1：明確該問題可用回溯法求解姐呐，它的解空間可以使用子集樹來表示。
2：計(jì)算出各個(gè)物品的單位重量?jī)r(jià)值分別為：{0.88,1,0.83,2.25,0.699};
講這些物品按照單位重量?jī)r(jià)值遞減的順序排列：{4kg,2.5kg,3.4kg,6kg,9.0kg}
3:按照這個(gè)排序我們先裝入物品4和物品2以及物品1典蝌；此時(shí)背包中已經(jīng)裝入了9.9kg的物品了曙砂；還剩下0.1kg;我們將再裝入0.1kg的物品3；最終得到的總價(jià)值為：14.58;我們可以知道這個(gè)實(shí)例的優(yōu)值不會(huì)超多14.58骏掀；
4：按照上述回溯順序我們繼續(xù)計(jì)算最終得出按照上述方法裝載所得到的解就是最優(yōu)解鸠澈；
上代碼：

package huisuo;
import java.util.Arrays;
public class Package {
    //先定義一個(gè)類，用來表示物品
    class MyElement implements Comparable{
        //物品重量
        float weight;
        //物品價(jià)值
        float value;
        //是否帶走物品
        boolean take = false;
        public MyElement(float w,float v){
            this.weight = w;
            this.value = v;
        }
        //比較物品的均值：用來排序
        @Override
        public int compareTo(Object o) {
            MyElement o1 = (MyElement)o;
            float currentR = value/weight;
            float R = o1.value/o1.weight;
            if(currentR<R){
                return 1;
            }else{
                return -1;
            }
        }   
    }
    
    private MyElement[] myelements;//物品的集合
    private float S;//背包的容量
    private float nowWeight;//記錄當(dāng)前已經(jīng)裝載的物品的總重量
    private float nowPrice;//記錄當(dāng)前已經(jīng)拿到物品的總價(jià)值
    private float betterPrice;//記錄當(dāng)前已經(jīng)裝的物品的最好價(jià)格
    public Package(float[] w,float[] v,float s){
        int len = w.length;
        this.S = s;
        myelements = new MyElement[len];
        for(int i =0;i<len;i++){
            myelements[i] = new MyElement(w[i],v[i]);
        }
        //默認(rèn)是從小到大排序砖织，但是我們將其改了款侵。此時(shí)排序是從大到小侧纯；
        Arrays.sort(myelements);
        System.out.println("物品的價(jià)值為："+"  "+"物品重量新锈！");
        for(int i = 0;i<len;i++){
            System.out.print(myelements[i].value+"       "+myelements[i].weight);
            System.out.println();
        }
    }
    /**
     * 用于打印已經(jīng)裝入背包的物品
     * @param myelements
     */
    public void Output(MyElement[] myelements){
        System.out.println("現(xiàn)在裝入的物品為(重量)：");
        int len = myelements.length;
        for(int i = 0 ;i<len;i++){
            if(myelements[i].take){
                System.out.print(myelements[i].weight+"   ");
            }
        }
    } 
    /**
     * 遞歸搜索這顆樹
     * @param t 表示遞歸樹的層數(shù)
     */
    public void traceBack(int t){
        if(t>=myelements.length){
            System.out.println("已經(jīng)找到合適的策略");
            betterPrice = nowPrice;
            Output(myelements);
            return;
        }
        //首先進(jìn)入左子樹
        if(nowWeight+myelements[t].weight<S){
            //進(jìn)入左子樹
            nowWeight += myelements[t].weight;
            nowPrice += myelements[t].value;
            myelements[t].take = true;
            traceBack(t+1);
            nowWeight-=myelements[t].weight;
            System.out.println("恢復(fù)現(xiàn)場(chǎng)");
            //恢復(fù)現(xiàn)場(chǎng)
            nowPrice -= myelements[t].value;
            myelements[t].take = false;
        }else{
            float rightP=bound(t+1);
            System.out.println("aaaaaaaaaa"+rightP);
            if(rightP>betterPrice){
                traceBack(t+1);
            }
        }
    } 
    /**
     * 查詢裝載當(dāng)前節(jié)點(diǎn)右子樹的節(jié)點(diǎn)時(shí)的總價(jià)值
     * @param i
     * @return
     */
    public float bound(int i){
        //計(jì)算當(dāng)前給右背包留下的容量
        float cleft = S - nowWeight;
        //右子樹如果一個(gè)節(jié)點(diǎn)都裝不下時(shí)；最好的價(jià)值仍然是當(dāng)前的價(jià)值
        float bound = nowPrice;
        int len = myelements.length;
        while(i<len && cleft>myelements[i].weight){
            cleft -=myelements[i].weight;
            bound+= myelements[i].value;
            i++;
            myelements[i].take = true;
        }
        return bound;
    }
    public static void main(String[] args) {
        float[] w = {3.4f,2.5f,6f,4f,9.0f};
        float[] v = {3f,2.5f,5f,9f,6.2f};
        float s = 10;
        Package package1 = new Package(w,v,s);
        package1.traceBack(0);
    }
}