子集树：当所给的问题是从n个元素的集合S中找出S满足某种性质的子集时，相应的解空间树称为子集树。例如0-1背包问题。这类子集树通常有2的n次方个叶结点，其结点总数为2的n+1次方减一个结点。遍历子集树算法需O(2的n次方)计算时间
排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n！个叶结点。因此，遍历排列树需要O(n!)计算时间。

子集树如图：

排列树如图：

装载问题

一、问题描述

1.有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且∑wi≤C1+C2，装载问题要求确定一个合理的装载方案可将这n个集装箱装上这2艘轮船。
2.容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：
(1) 首先将第一艘轮船尽可能装满；
(2) 将剩余的集装箱装上第二艘轮船。
3.将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。

二、算法设计

1.用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。可行性约束函数可剪去不满足约束条件的子树。在子集树的第j+1层的结点Z处，用cw记当前的装载重量，当 cw＞C1 时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。可以引入一个限界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。

package backtrack;

public class Loading {

    //类数据成员
    static int n; //集装箱数
    static int[] w; //集装箱重量数组
    static int c; //第一艘轮船的载重量
    static int cw; //当前放进轮船的集装箱重量
    static int bestw; //当前最优载重量
    static int r; //剩余在岸上的集装箱重量
    static int[] x;  //当前解
    static int[] bestx;  //当前最优解

    public static int maxLoading(int[] ww,int cc,int[] xx) {

        //初始化类数据成员
        n=ww.length-1;
        w=ww;
        c=cc;
        cw=0;
        bestw=0;
        r=0;
        x=new int[n+1];
        bestx=xx;
        //集装箱还没装上轮船前，岸上剩余集装箱重量是所有集装箱重量之和
        for(int i=1;i<=n;i++)
            r+=w[i];

        //计算最优载重量
        backtrack(1); //backtrack(i)搜索子树的第i层，这里都是从第一个集装箱开始回溯
        return bestw;

    }

    //回溯算法
    private static void backtrack(int i) {

        //搜索第i层结点
        if(i>n) {  //n是集装箱个数，搜索层数大于n，说明搜索到达叶结点
            if(cw>bestw) {
                for(int j=1;j<=n;j++)
                    bestx[j]=x[j];
                bestw=cw; //得到最优载重量
            }
            return;
        }

        //搜索子树
        r-=w[i];  //搜索到第i个集装箱，无论它是否能放进轮船，剩余载重量都要除去这个集装箱

        //搜索左子树，有约束条件
        if(cw+w[i]<=c) {  //当前轮船内的集装箱重量加上第i个集装箱重量要小于轮船载重量才可以被放进轮船，这是约束条件
            x[i]=1;
            cw+=w[i]; //当前重量要加上第i个要放进轮船的集装箱的重量
            backtrack(i+1);  //搜索子树下一层
            cw-=w[i];  //返回到上一层，要还原当前重量
        }
        //搜索右子树
        if(cw+r>bestw) {  //限界函数，当前重量加上剩余在岸上的重量大于最优载重量则说明有可能找到更优解
            x[i]=0;
            backtrack(i+1);  //进行回溯
        }
        r+=w[i];  //岸上剩余重量还原
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] ww= {0,5,2,1,3};
        int[] xx=new int[ww.length+1];
        for(int i=1;i<=ww.length;i++)
            xx[i]=0;
        maxLoading(ww,10,xx);
        System.out.println("装入轮船1的集装箱有：");
        for(int j=1;j<=ww.length;j++)
            if(bestx[j]==1)
                System.out.print(j+" ");
        System.out.println();
        System.out.print("最优载重量为："+bestw);


    }

}

运行结果

三、复杂度分析

装载问题的解空间是一棵子集树，共有2的n次方叶个结点，所以时间复杂度为O(2的n次方)