算法设计与分析之回溯法

（一）装载问题

问题描述

用回溯法编写一个递归程序解决如下装载问题：有 n 个集装箱要装上 2 艘载重分别为 c1 和 c2的轮船，其中集装箱 i 的重量为 wi（1≤ i ≤ n），且∑ 𝑤𝑖 ≤ 𝑐1 + 𝑐2 𝑛 𝑖=1 。问是否有一个合理的装载方案可以将这 n 个集装箱装上这 2 艘轮船？如果有，请给出装载方案。
举例：当 n=3，c1=c2=50，且 w=[10,40,40]时，可以将集装箱 1 和 2 装到第一艘轮船上，集装箱 3 装到第二艘轮船上；如果 w=[20,40,40]时，无法将这 3 个集装箱都装上轮船。

输入格式

输入的第一行整数c，第一艘轮船载重量。
　　以后两行分别为每个集装箱的重量

输出格式

输出2行，第一行包含一个整数，表示最大载重量
接下来依次输出装入的集装箱序号

样例输入

10
w[]={0,3,5,6,8};

样例输出

最大载重量为：9
构造最优解 :0 1 0 1 0

回溯法：

回溯法又称为试探法。回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。
回溯算法的基本思想是：在一条路上往前走，如果能走就走，如果不能走就退回来，然后换一条路再进行试探。

问题分析

可以将最优装载分成两部分来进行考虑

第一部分是轮船一的最大载重问题，和背包问题比较相似
第二部分就是判断轮船一是否可以装剩下的问题

问题一需要通过判断节点i（集装箱i）的装载与不装载形成一个二叉树，从根节点到叶子节点是畅通的便是一种方案。
用一个变量存储来存储此时此刻的重量，以便于用来记录最优的装载方案。
可以设 bestw : 表示当前的最优载重量,
curw : 当前扩展结点Z的载重量 ;
remain : 剩余集装箱的重量;
w[i] : i节点（i集装箱）的重量;
当 curw+w[i]<=c1时可以放
当 curw + remain (限界函数) <= bestw时，可将Z的右子树剪去。（此时右子树的所有方案一定大于轮船1的载重量）
当 curw + remain (限界函数) > bestw时，可以讨论i节点不放的情况。

伪代码：

①用i来记录是第几个集装箱，并判断该集装箱是否可以装入
②如果剩余的载重量大于该集装箱的重量，就先不装入，否则装入。
③继续判断，如果先不放该集装箱，再放剩下的集装箱的话是否可以达到最优装载。
④利用回溯法，逐个判断集装箱，直到结束。

代码

java

package Practise915;
import java.util.Scanner;
public class BackT {
		//类数据成员
		static int n;    //集装箱数
		static int[] w;   //集装箱重量数组
		static int c;    //第一艘轮船的载重量
		static int cw;   //当前载重量
		static int bestW;   //当前最优载重量
		static int remain;    //剩余集装箱重量
		static int[] curx;   //当前解
		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;
			curx = new int[n+1];
			bestX = xx;
			
			//初始化r
			for (int i = 0; i <= n; i++) {
				remain += w[i];
			}
			
			//计算最优装载重量
			backTrack(1);
			return bestW;
		}

		private static void backTrack(int i) {
			// 搜索第i层子节点
			if (i > n) {  //到达叶子节点
				if (cw > bestW) {
				    for (int j = 0; j <= n; j++) {
						bestX[j] = curx[j]; 
					}
					bestW = cw;
				}
				return;
			}
			//搜索子树
			remain -= w[i];
			if (cw + w[i] <= c) {  //如果没有超重
				//搜索左子树
				curx[i] = 1;
				cw += w[i];
				backTrack(i+1);  //搜索孩子节点
				cw -= w[i];
			}if (cw + remain >= bestW) {
				curx[i] = 0;    //搜索右子树
				backTrack(i+1);
			}
			remain += w[i];
		}

		public static void main(String[] args) {
			Scanner input = new Scanner(System.in);
			System.out.println("集装箱个数：");
			int n = input.nextInt();
			System.out.println("最大载重量：");
			int c = input.nextInt();
			System.out.println("每个集装箱的重量：");
			int[] w = new int[n];
			for (int i = 0; i < n; i++) {
				w[i] = input.nextInt();
			}
			int[] x = new int[n];
			maxLoading(w, c, x);
			System.out.println("最大载重量:"+bestW);
			System.out.println("装入的集装箱序号:");
			for (int i = 0; i < n; i++) {
				System.out.print(bestX[i] + " ");
			}
		}

}

运行结果

c++

#include<iostream>
using namespace std;
class loading{
    friend int MaxLoading(int w[],int c, int n,int bestx[]);
    private:
        void backtrack(int t);
        int n,c,*x,*bestx;//件数，载重量，当前解向量，当前最优解向量
        int *w,cw,r,bestw; //重量信息，目前部分解的重量，目前剩余物品的总重量，最优解的重量
};
 
void loading::backtrack(int t){
    //已经到达叶子节点，一定是最优解
    if(t>n){
        for(int i=0;i<n;i++) 
            bestx[i]=x[i];
        bestw=cw;
        return;
    }
     r-=w[t];
    //考虑左子树选择t
    if(cw+w[t]<=c){ //可以放进去的话,为1的左子树可以进入
        cw+=w[t];
        x[t]=1;
        backtrack(t+1);
        cw-=w[t];
    }
    //考虑右子树不选择t
    if(cw+r<bestw){//就算其余的全部放进去都没有当前最优解的bestw大，那就剪枝，这个点变为死结点
        r+=w[t];
        return;
    }
    //为0的右子树可以进入
    else{
    	 x[t]=0;
    	backtrack(t+1);
    }
   
    //这个点变为死结点了，回溯
    r+=w[t];
}
int MaxLoading(int w[],int c,int n,int bestx[]){
    loading X;
    //初始化
    X.x=new int[n+1];
    X.w=w;
    X.c=c;
    X.n=n;
    X.bestx=bestx;
    X.bestw=0;
    X.cw=0;
    X.r=0;
    for(int i=1;i<=n;i++){
        X.r+=w[i];
    }
    //从第一个结点开始
    X.backtrack(0);
    delete[]X.x;
    return X.bestw;
}

int main()
{
	int c,n;
	int bestw;
	cout<<"集装箱个数:"<<endl; 
	cin>>n;
	int w[n];
	int bestx[n];
	cout<<"最大载重量:"<<endl;
	cin>>c;
	cout<<"每个集装箱的重量:"<<endl;
	for(int i=0;i<n;i++)
		cin>>w[i];
	bestw=MaxLoading(w,c,n,bestx);
	cout<<"最大载重量:"<<bestw<<endl;
	cout<<"装入的集装箱序号:"<<endl;
	for(int i=0;i<n;i++)
		cout<<bestx[i]<<" ";
	cout<<endl;
	return 0;
}

运行结果

（二）8皇后问题

问题描述

要求用回溯法求解 8-皇后问题，使放置在 8*8 棋盘上的 8 个皇后彼此不受攻击，即：任何两个皇后都不在同一行、同一列或同一斜线上。请输出 8 皇后问题的所有可行解。

问题分析

解决八皇后问题，如果采用穷举法，那么需要列举8^8种情形。而采用回溯法，则是对解空间使用深度优先遍历的方式找到可行解，然后用限制条件来缩小解空间。

解题思想

①用数组 x来存放，用下角标表示第几行，数组中的值代表该行中的那一个位置。设一个变量k，代表此时在下第几行。
②封装一个用来判断是否符合条件（不同列，不在对角线上）的函数，利用列不能相同，列之差与行之差不能相同判断，不符合条件的直接跳过（缩小解空间）来简化。
③用for循环，将满足条件的可行解放入到x数组中，当数组x填满后，就输出，此时一种方案结束。
④利用递归，直到所有可行方案输出，结束。
以上便是本题的一些思路

代码

#include <iostream>
#include <cmath>
using namespace std;
int num=0;
bool Location(int k,int i,int *x)
{
    for(int j=0;j<k;j++) //j此时代表第几行
        if((i==x[j])||(abs(k-j)==abs(i-x[j])))
		//判断是否同一列     判断是否在对角线上（利用两直角边长度相同）
        	return false;
    return true;
}
void Queen (int k,int n,int *x)
{
    for(int i=0;i<n;i++)
    {
        if(Location(k,i,x))
        {
            x[k]=i;
            if(k==n-1)
            {
                for(int i=0;i<n;i++)
                    cout<<x[i]<<" ";
                num++;
                cout<<endl;
            }
            else
                Queen(k+1,n,x);
        }
    }
}
void Queen (int n,int *x)
{
    Queen(0,n,x);
}

int main()
{
    int n=8;
    int x[8];//下标代表第几行，值代表放在该行哪个位置
    for(int i=0;i<n;i++)
        x[i]=-1;
    Queen(8,x);
    cout<<"一共有"<<num<<"种组合"<<endl;
    return 0;
}