一、上机目的

1、通过回溯法的示例程序理解回溯法的基本思想；
2、运用回溯法解决实际问题进一步加深对回溯法的理解和运用；

二、上机内容与要求

1、分析并掌握“装载问题” 的回溯法求解方法；
2、练习使用回溯法求解“符号三角形问题”

三、上机步骤

1．理解回溯算法思想和算法示例；
2．上机输入和调试算法示例程序；
3．理解实验题的问题要求；
4．上机输入和调试自己所编的实验题程序；
5．验证并分析实验题的实验结果；
6．整理出实验报告；

四、上机结果

1、将课本5.2节算法改为程序，并输入数据及进行测试；

import java.util.Scanner;
public class MaxLoading {static final int NUM = 100;// 集装箱重量static int[] w=new int[NUM];// 最优解static int[] bestX = new int[NUM];// 当前解static int[] x= new int[NUM];// 最优装船重量static int bestW = 0;// 物品个数static int n;// 第一个船的载重量static int c1;// 第二个船的载重量static int c2;// 当前已装船重量static int cw = 0;private static int bound(int t) {// 初始化剩余重量int rw = 0;for (int i = t+1;i <= n;++i) {// 计算剩余集装箱重量rw += w[i];}// 返回可装的总重量return rw+cw;}/*** 回溯法* @param t :第几个集装箱*/public static void loadingRec(int t) {if (t > n) { // 集装箱装箱完毕if (cw > bestW) {  // 如果当前重量大于最优重量// 更新最优重量bestW = cw;for (int i = 1; i <= n; i++) {// 最优解更新为当前解bestX[i] = x[i];}}return;}else { // 尚未结束装箱if (cw + w[t] <= c1) { // 若装入当前集装箱，且重量小于船载重量// 加上此集装箱重量cw +=w[t];// 选择该集装箱x[t] = 1;// 下一个loadingRec(t+1);cw -= w[t];x[t] = 0;}if (bound(t) > bestW) { // 不装第t个集装箱，若总重量大于最优重量loadingRec(t+1);}}}public static void main(String[] args) {Scanner in = new Scanner(System.in);System.out.print("请输入集装箱的个数：");n = in.nextInt();System.out.println("请输入集装箱的重量(整数）：");for (int i = 1; i <= n;++i) {w[i] = in.nextInt();}in.nextLine();System.out.print("请输入第一船的载重量：");c1 = in.nextInt();in.nextLine();System.out.print("请输入第二船的载重量：");c2 = in.nextInt();loadingRec(1);System.out.println("第一船的最优重量为：" + bestW);System.out.println("第一船的最优解为：");for (int i = 1; i <= n;++i) {if (bestX[i] == 1) { // bestX[i] == 1，表示选中System.out.println("物品" + i + "装入第1个集装箱");}}int cw2 = 0;for (int i = 1;i <= n;++i) {// 计算剩余重量if (bestX[i] == 0) {cw2 += w[i];}}// 剩余重量小于第二个船的载重量，可以装入// 下行为小于第二艘船的载重量if (cw2 <= c2) {System.out.println("可以将剩余集装箱装入第二船，问题有解");}else { // 剩余重量大于第二个船的重量，不能装入System.out.println("不能将剩余集装箱装入第二船，问题无解");}in.close();}
}

2、自学5.4节，并完成符号三角形问题。

import java.util.Scanner;/*** 符号三角形问题* @author Jaick**/
public class Triangles {public int n;//第一行的符号个数public int half;//n*(n+1)/4public int count;//当前+的个数public int[][] p;//符号三角形矩阵public long sum;//已找到的符号三角形个数public long compute(int nn){n=nn;count=0;sum=0;half=n*(n+1)/2;if(half%2==1) return 0;half=half/2;p=new int[n+1][n+1];backtrack(1);return sum;}public void backtrack(int t){if(count>half||(t*(t-1)/2-count)>half)return ;if(t>n)sum++;else{for(int i=0;i<2;i++){p[1][t]=i;count+=i;for(int j=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//^：按位异或。比如二进制     1001 ^ 1100 = 0101  0^0=0，1^1=0 ，1^0 = 1，0^1=1。count+=p[j][t-j+1];}backtrack(t+1);for(int j=2;j<=t;j++){count-=p[j][t-j+1];}count-=i;}}}public static void main(String[] args) {Scanner in =new Scanner(System.in);Triangles t=new Triangles();System.out.println("Input:");int n=in.nextInt();long sum=t.compute(n);System.out.println("Output:");System.out.println("n="+t.n+"时，有"+sum+"个符号三角形");}
}