文档介绍：一、实验题目
回溯法
二、实验目的
掌握回溯法的基本思想。
掌握回溯法中问题的解空间、解向量、显式约束条件、隐式约束条件以及子集树与排列树的递归算法结构等内容。
掌握回溯法求解具体问题的方法。
三、实验内容
有一批共n;
〃计算最优装载重量
backtrack(0);
return bestir;
public static void backtrack(int i)(
〃搜索第i层结点
if(i>n)( 〃到达叶结点
if (cw>/?estiv)(
for(int j=0;j<=n;j++) bestx[j]=x[j];
bestM=cw;
}
return;
}
r-=w[i];
if(cw+w[i]<=c){//搜索左子树
x[i]=l;
cw+=w[i];
backtrack(i+l);
cw-=w[i];
}
if (cw+r>besth/)(
x[i]=0;
backtrack(1+1);
}
r+=iv[i];
}
public static void main(String[] args) {
Scanner in=new Scanner();
System .out. println(H请输入集装箱的数目：“)； int p =();
int []ww=new int[p];
System .out. printin ("请输入各集装箱的重量：");
for(int i=0;i<;i++)
{
ww[i]=();
}
System. out. printin (”请输入第一艘轮船的载重量：");
int cc=();
int []xx=new int[];
maxLoading^vi, cc,xx);
System .out. print (”输出当前最优解;
for(int i = 0;i<;i++)
(xx[i]+"");
//("\n");
("当前最优载重量为："+best“)；
} }
【运行结果】
!请输入集装箱的数目：
请输入各集装箱的重量：
5 10 12 15 1S 20
请输入第一艘轮船的载重量：
25
精出当前最优解:1 0 0 0 0 1当前最优载重量为：25
2、 N后问题
【问题分析】
首先找出解空间：给棋盘的行和列都编上1到N的号码，皇后也给编上1到N的号码。由于一个皇后应在不同的行上，为不失一般性，可以假定第i个皇后将放在第i行上的某列。因此N皇后问题的解空间可以用一个N元组(XI, X2, .....Xn)来表示，其中Xi是放置皇后i所在的列号。这意味着所有的解都是N元组(1, 2, 3, ......., N)的置换。解空间大小为N!。其次我们看约束条件：因为解空间己经给我们排除了不在同一行(因为每个皇后分别己经对应不同的行号)的约束条件。我们要判断的是不在同一列和不在同一斜线的约束。因为Xi表示皇后所在的列号，所以如果存在X (