JAVA面向对象---实现回溯算法中的装载问题

当然,我们先要确定货物的总重是否大于两艘船总容量之和 , 若大于则问题肯定无解.
解决的方法还是很容易得出的 : 我们任意选择一艘船 , 尽可能的多装一些货物进去,找到一个方案使得我们选择的船尽可能的多装货物 (不妨选择 shipOne ) 换一句话说 就是使得shipOne装了货物后剩下的间隙或者说余容量 (Margin)最小 . 然后计算 剩下没装的货物的总重量 是否大于 shipTwo 的容量如果不大于(可以刚好等于) 则说明问题有解,本问题就得到解决.

前面提到 , 回溯法是将问题的 解 抽象成 图或者树的结构来表示.

在装载问题中,对于每个货物我们的选择只有 选择 / 不选 所以我们选择抽象成树的结构,对于选择此货物自然对应 1/true 对于不选择此货物对应 0/true , 依次对每个货物进行选择,我们自然会得到 2^n个解
但是我们当然没有必要把所有结果都列举出来, 例如以下例子 :

W 为货物的重量的集合,c1,c2为两艘船的总容量,设置判断条件为: 已经装上的 货物重量 加上 下一个货物 后的重量不大于shipOne的容量,那么就可以装上此货物 .若大于则选择不装此货物 这样自然就可以得到一棵得到 优化结果集的子树 .

但是经过第一轮的选择之后,虽然得到了第一个方案,但是我们不能保证这是最优的解 , 不能确定是最优的方案就不能保证我们的问题是否有解 , 所以只有经过多轮不同的选择 才能得到最优的方案,才能得出问题是否有解.

那么 , 如何进行多轮的选择? 怎么才能知道 哪一轮选择的方案是最好的? 前面提到余容量就是我们判断是否是更优方案的指标
剩余容量越小,则说明这样的方案更优.

知道如何判断是否是更优的方案之后,我们就要思考如何遍历这棵树能更快的得出结果集,如果从头开始遍历,自然是效率最低选择,因为我们会重复走我们已经走过的路. 所以我们不妨进行回溯, 如下图所示: 我们第一轮得出的结果是

90+0+40+0+20+0+0 ,于是从最后一个货物 ( 重量为10的货物开始回溯 ) 对于已经选择为 0/false 的物品我们自然不需要再去遍历它的左子树了,因为我们本身就装不下它 . 所以我们去遍历右子树 . 于是我们往上回溯 , 找到以第一个我们已经选择的货物 ,我们这一轮
( 第二轮从选择重量为20的货物开始 ) 就不装载 重量为 20的货物, 我们想要去选择剩下的其余货物(12 和 10).进行第二轮的选择后 会得到一个解决方案,我们自然就可以比较 余量(Margin) 是否较前一种方案更优 接着我们继续回溯…一直到我们进行最后一轮回溯 , 最后一轮便是从我们之前选择的第一个货物开始,一来就不装载 ( 重量为90的货物 ) 此货物. 最后进行一轮选择. 最后就可以得到我们的最优方案 , 以此便可以确定我们的问题 , 是否有解.

在使用Java编程的时候,我们一定要贯彻面向对象的思想.
装载问题的实现代码如下：

public class BackTrackAlgorithm {
	
	//声明全部所需的变量,我们需要装载的货物重量,它的总重量,两艘船,货物对象.

    static int aboutCargo[]={90,80,40,30,20,12,10};
    static int totalWeight;
    static Ship shipOne;
    static Ship shipTwo;
    static Cargo[] cargo=new Cargo[aboutCargo.length];
    static Cargo[] realCargo=new Cargo[aboutCargo.length];  //不用先思考readlCargo的作用在后面会给出解释
    static int i=0;	//见后


	//在main中直接调用两个方法得出解
    public static void main(String[] args) {

        BackTrackAlgorithm bta=new BackTrackAlgorithm();
        bta.init();
        bta.getResult();


    }
    //初始化船,并使用回溯法,使得我们的问题得出最优方案
    public void init(){

        for (int j = 0; j < aboutCargo.length; j++) {
            cargo[j]=new Cargo();
            realCargo[j]=new Cargo();
            realCargo[j].weight=aboutCargo[j];
            cargo[j].weight=aboutCargo[j];
            totalWeight+=aboutCargo[j];
        }

        shipOne=new Ship(152,cargo,realCargo);
        shipTwo=new Ship(130);
		
		//开始建立树结构
        while (true) {
        	//进行每一轮的选择
            while(i<shipOne.numOfCargo){
                if((shipOne.nowWeight+shipOne.cargo[i].weight)<=shipOne.capacity){//判断条件
                    shipOne.nowWeight+=shipOne.cargo[i].weight;//变化当前重量和余量以及是否装载上船
                    shipOne.nowMargin-=shipOne.cargo[i].weight;
                    shipOne.cargo[i].isLoad=true;
                        i+=1;
                }
                else {
                    shipOne.cargo[i].isLoad=false;//不装载,继续往下走
                    i+=1;
                }
            }
			//进行一轮的选择之后是否得到更优的方案
            if(shipOne.nowMargin< shipOne.minMargin){

                shipOne.minMargin= shipOne.nowMargin;
				//如果得到更优的方案,我们需要存入这一轮的货物选择情况,为什么要使用另一个realCargo数组,请阅读代码后思考片刻
                for (int j = 0; j < shipOne.numOfCargo; j++) {
                    if(shipOne.cargo[j].isLoad==true){
                        shipOne.realCargo[j].weight=shipOne.cargo[j].weight;
                        shipOne.realCargo[j].isLoad=true;
                    }
                    if(shipOne.cargo[j].isLoad==false){
                        shipOne.realCargo[j].isLoad=false;
                        shipOne.realCargo[j].weight=shipOne.cargo[j].weight;
                    }
                }
            }
            
			//进入回溯法,回溯的就是我们之前设置的静态属性 i 即我们选择的货物货号
            i=backtrace(i-1);//为什么是 i-1:烦请思考片刻
			
			//退出的条件,我们是否已经结束最后一轮.
			 if(i==0) {
                return;
            }
        }


    }
    //回溯法
    public int backtrace(int j){
    		//请读者思考作用.
            while(j>0&&shipOne.cargo[j].isLoad==false){
                j-=1;
            }
            //请读者思考作用.
            if(shipOne.cargo[j].isLoad==true){
                shipOne.cargo[j].isLoad=false;
                shipOne.nowMargin+=shipOne.cargo[j].weight;
                shipOne.nowWeight-=shipOne.cargo[j].weight;

                j+=1;
            }
            return j;
            
            /**
            *  tips:这里每轮的回溯会改变shipOne.cargo[i].isLoad,最后得到的自然是最后一轮选择方案,
            *  但最后一轮得到的不一定是最优解,所以我们肯定需要另外一个Cargo数组来记录更优方案 即前面
            *  声明的readCargo[]
			*/
    }
    
    //返回最优结果集
    public void getResult(){
		//判断是否有解
        if((totalWeight-(shipOne.capacity-shipOne.minMargin))<=shipTwo.capacity){

            System.out.println("\n本问题有合理的方案.\n");

            for (int j = 0; j < aboutCargo.length; j++) {
                if(shipOne.realCargo[j].isLoad==true) {
                    System.out.println("货物 " + j + " 已经装载上船1,重量是:" + shipOne.realCargo[j].weight);
                }
//                if(shipOne.realCargo[j].isLoad==false) {
//                    System.out.println("货物 " + j + " 将会装载上船2,重量是:" + shipOne.realCargo[j].weight);
//                }
            }
        }
        else{
            System.out.println("经过努力的尝试,得出本问题没有合理的方案使得全部货物装上两艘船,抱歉");
        }

    }

}

class Ship{

    int capacity=0;
    int minMargin;	//目前得到的最小余量(不断缩小)
    int nowMargin; //现在的船上余量
    int nowWeight; //现在船上货物的重量
    int numOfCargo;
    Cargo []cargo;
    Cargo []realCargo;

    public Ship(int capacity){
        this.capacity=capacity;
        this.minMargin=capacity;
        this.nowMargin=capacity;
    }
	//这里使用重载是为了区分两艘船的作用.
    public Ship(int capacity,Cargo cargo[],Cargo realCargo[]){
        this.capacity=capacity;
        this.cargo=cargo;
        this.realCargo=realCargo;
        this.numOfCargo= cargo.length;
        this.minMargin=capacity;
        this.nowMargin=capacity;
        this.nowWeight=0;
    }

}

class Cargo{
		
    int weight=0;
    boolean isLoad=false;

}

代码如下（示例）：

本问题有合理的方案.

货物 0 已经装载上船1,重量是:90
货物 2 已经装载上船1,重量是:40
货物 5 已经装载上船1,重量是:12
货物 6 已经装载上船1,重量是:10

这里对文章进行总结：

在明白回溯法的本质之后,相信读者一定能写出更为优雅和简洁的程序.
感谢您的耐心阅读.