• 回溯算法的应用

    基本思想：

    回溯法从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。在当前扩展结点处,搜索向纵深方向移至一个新结点。这个新结点成为新的活结点,开成为当前扩展结点。如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)至最近的活结点处,并使这个活结点成为当前扩展结点。回溯法以这种工作方式递归地在解空间中搜索,直至找到所要求的解或解空间中已无活结点时为止。

    例：对于n=3时的0-1背包问题,考虑下面的具体实例:w=[16,15,15],p=[45，25,25],c=30。

    解空间：(三种物品的所有可能)

    每一层的根节点对应某种物品。第一层是第一件物品，第二层时第二件物品，第三层是第三件物品。左子树表示装入下一件物品，右子树表示不装下一件物品

    • 开始时,根结点是唯一的活结点,也是当前扩展结点。在这个扩展结点处,可以沿纵深方向移至结点B或结点C。
    • 假设选择先移至结点B。此时,结点A和结点B是活结点,结点B成为当前扩展结点。由于选取了w1,故在结点B处剩余背包容量是r=14,获取的价值为45。
    • 从结点B处,可以移至结点D或E。由于移至结点D至少需要w2=15的背包容量,而现在仅有的背包容量是r=14,故移至结点D导致不可行解。搜索至结点E不需要背包容量,因而是可行的。从而选择移至结点E。此时,E成为新的扩展结点,结点A,B和E是活结点。在结点E处,r=14,获取的价值为45。
    • 从结点E处,可以向纵深移至结点J或K。移至结点J导致不可行解,而移向结点K是可行的,于是移向结点K,它成为新的扩展结点。由于结点K是叶结点,故得到一个可行解。这个解相应的价值为45。Xi的取值由根结点到叶结点K的路径唯一确定,即x=(1,0,0)。
    • 由于在结点K处已不能再向纵深扩展,所以结点K成为死结点。返回到结点E处。此时在结点E处也没有可扩展的结点,它也成为死结点。接下来又返回到结点B处。结点B同样也成为死结点,从而结点A再次成为当前扩展结点。
    • 结点A还可继续扩展,从而到达结点C。此时,r=30,获取的价值为0。
    • 从结点C可移向结点F或G。假设移至结点F,它成为新的扩展结点。结点A,C和F是活结点。在结点F处,r=15,获取的价值为25。从结点F,向纵深移至结点L处,此时,r=0,获取的价值为50。由于L是叶结点,而且是迄今为止找到的获取价值最高的可行解,因此记录这个可行解。
    • 结点L不可扩展,又返回到结点F处。按此方式继续搜索,可搜索遍整个解空间。搜索结束后找到的最好解是相应0-1背包问题的最优解。

    回溯算法的装载问题

    有一批共n个集装箱要装上两艘载重量分别为C_{1}和 C_{2}的轮船,其中,集装箱 i 的重量为W_{i}，

    \sum_{i=1}^{n}w_{i}=c_{1}+c_{2}
    装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船。如果有,找出一种装载方案。

    基本思路：

    (1）首先将第一艘轮船尽可能装满。

    (2）将剩余的集装箱装上第二艘轮船。
    将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。由此可知,装载问题等价于以下特殊的0-1背包问题。
    将每个物品的装与不装化成解空间

    回溯算法思想

    算法maxLoading调用递归方法 backtrack(1)实现回溯搜索。backtrack(i)搜索子集树中第i层子树。

    类Loading 的数据成员记录子集树中结点信息

    cw记录当前结点相应的装载重量

    bestw记录当前最大装载重量。


    在算法backtrack 中

    当i≥n时,算法搜索至叶结点,其相应的装载重量为cw。如果cw>bestw ,则表示当前解优于当前最优解,此时应更新bestw。
    当i≤n时,当前扩展结点Z是子集树的内部结点。该结点有:x[i]=1和x[i]=0两个儿子结点。

    其左儿子结点表示x[i]=1的情形,仅当cw＋w[i]≤c时进入左子树,对左子树递归搜索。

    其右儿子结点表示x[i]=0的情形。由于可行结点的右儿子结点总是可行的,故进入右子树时不需检查可行性。 

    1. public class Loading {
    2.     //类数据成员
    3.     static int n;   //集装箱数
    4.     static int[] w;//集装箱重量数组
    5.     static int c;//第一艘轮船的载重量
    6.     static int cw;//当前载重量
    7.     static int bestw;//当前最优载重量
    8.     private static int maxLoading(int[]ww,int cc){
    9.         //初始化数据成员
    10.         n=ww.length-1;
    11.         w=ww;
    12.         c=cc;
    13.         cw=0;
    14.         bestw=0;
    15.         
    16.         //计算最优载重量
    17.         backtrack(1);
    18.         return bestw;
    19.     }
    20.  
    21.     private static void backtrack(int i) {
    22.         //搜索第i层结点
    23.         if (i>n){//到达叶子节点
    24.             if (cw>bestw) bestw =cw;  //更新最优载重
    25.             return;
    26.         }else{//未到达叶子节点
    27.             if (cw+w[i]<=c){  //表示装上i层的节点后还能继续装
    28.                 cw+=w[i];//更新当前载重
    29.                 backtrack(i+1);//搜索下一层，直至搜索玩所有左子树，再遍历右子树
    30.                 cw-=w[i];//恢复遍历某个左节点之前的最初状态，便于遍历右子树
    31.             }
    32.             backtrack(i+1);//遍历右子树，无需装入，直接下一层
    33.         }
    34.     }
    35.  
    36. }

     上界函数

    cw+r表示i层之前已装的货物+i层之后剩余的重量，cw+r≤bestw表示当前最优载重量能装下i层之后所有货物，不需要再拿出货物，故不需要考虑右子树（不要考虑拿出某货物再装入更重的）

    在算法中记录与当前最优值相应的当前最优解。在类Loading中增加两个私有数据成员α和 bestx,x用于记录从根至当前结点的路径, bestx记录当前最优解。算法搜索到达叶结点处,就修正bestx的值。 

    1. public class Loading2 {
    2.     static int n;   //集装箱数
    3.     static int[] w;//集装箱重量数组
    4.     static int c;//第一艘轮船的载重量
    5.     static int cw;//当前载重量（重量）
    6.     static int bestw;//当前最优载重量（重量）
    7.     static int r;//剩余集装箱重量、
    8.     static int[] bestx;//记录当前最优解（路径）
    9.     static int[]x;//当前解（路径）
    10.     public static int maxLoading(int []w, int c, int[] bestx){
    11.         //迭代回溯法
    12.         //返回最优载重及其相应的解
    13.         //初始化根节点
    14.         int i =1;
    15.         int n=w.length-1;
    16.         int []x = new int[n+1];
    17.         bestw =0;
    18.         r=0;
    19.         for(int j=0; j<=n; j++){
    20.             r=r+w[j];
    21.         }
    22.         //搜索子树（进入子树）
    23.         while (true){
    24.             while (i<=n&&cw+w[i]<=c){//进入节点i的左子树，层数变为i+1
    25.                 r-=w[i];//剩余货物减少，节点i装入
    26.                 cw+=w[i];//当前载货量
    27.                 x[i]=1;//左子树，装入
    28.                 i++;//层数变化
    29.             }
    30.             if (i>n){
    31.                 //到达叶节点
    32.                 for (int j=1;j<=n;j++){
    33.                     bestx[j]=x[j];//每次到叶节点更新最佳路径解
    34.                 }
    35.                 bestw = cw;//更新最优装载值
    36.             }else {
    37.                 //进入右子树
    38.                 r-=w[i];//剩余货物减少，节点i装入，层数变为i+1
    39.                 x[i]=0;
    40.                 i++;
    41.             }
    42.             //从叶子节点返回根节点
    43.             while (cw+r<=bestw){
    44.                 //剪枝回溯
    45.                 i--;//回溯
    46.                 while (i>0&&x[i]==0){//未到根节点且为右子树
    47.                     r+=w[i];//从右子树返回
    48.                     i--;
    49.                 }
    50.                 if (i==0) return bestw;//回到根节点
    51.                 //进入右子树
    52.                 x[i]=0;
    53.                 cw-=w[i];
    54.                 i++;
    55.             }
    56.  
    57.         }
    58.     }
    59. }

    批处理作业调度问题

    批处理作业调度问题要从n个作业的所有排列中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架,设开始时x=[1,2,…,n]是所给的n个作业,则相应的排列树由x[1:n]的所有排列构成。
    类FlowShop 的数据成员记录解空间中结点信息,以减少传给backtrack 的参数。二维数组m是输人的作业处理时间。bestf记录当前最小完成时间和, bestx是相应的当前最佳作业调度。
    在递归方法 backtrack 中，当i>n时,算法搜索至叶结点,得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳作业调度。
    当i≤n时,当前扩展结点位于排列树的第i - 1层。此时算法选择下一个要安排的作业,以深度优先的方式递归地对相应子树进行搜索。对于不满足上界约束的结点,则剪去相应的子树。

    1. public class 批处理作业调度 {
    2.         static int n;//作业数
    3.         static int f1;//机器1完成处理时间
    4.         static int f;//完成时间和
    5.         static int bestf;//当前最优值
    6.         static int [][]m;//个作业所需的处理时间，m[i][1]表示作业i在机器1的处理时间
    7.         static int []x;//当前作业调度，x[i]=a表示第i个调用作业a
    8.         static int []bestx;//当前最优作业调度
    9.         static int []f2;//机器2完成处理时间，f2[i]表示作业i在机器2完成处理时间
    10.     private static void backtrack(int i){
    11.         if (i>n){//到达叶子节点
    12.             for (int j=1;j<=n;j++){
    13.                 bestx[j]=x[j];//最优路径更新
    14.             }
    15.             bestf=f;//最优值更新
    16.         }else {//未到达叶子节点
    17.             for (int j=i;j<=n;j++){//以当前节点
    18.                 f1+=m[x[j]][1];
    19.                 f2[i]=((f2[i-1]>f1) ? f2[i-1]:f1)+m[x[j]][2];//在作业i-1使用机器2的时候，使用机器1
    20.                 f+=f2[i];
    21.                 if (f//当前时间和小于最优则更新
    22.                     Math.swap(x,i,j);//以上发现最优值，交换调度顺序
    23.                     backtrack(i+1);//在以上基础，选择下一个要安排的作业
    24.                     Math.swap(x,i,j);//以节点i为基础的某一调度排列完成，再返回到节点i进行以i为基础的另一调度序列
    25.                 }
    26.                 f1-=m[x[j]][1];//f1也还原
    27.                 f-=f2[i];//f也还原
    28.             }
    29.         }
    30.     }
    31.  
    32. }

    时间复杂度为O(n!)

    符号三角形问题

    图是由14个“＋”号和14个“―”号组成的符号三角形。两个同号下面都是“＋”号,两个异号下面都是“ -   ”号。在一般情况下﹐符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n,计算有多少个不同的符号三角形,使其所含的“＋”和“一”的个数相同。

    对于符号三角形问题,用n元组x[1: n]表示符号三角形的第一行的n个符号。当[i]=1时,表示符号三角形的第一行的第i个符号为“＋”;当α[i]=0时,表示符号三角形的第一行的第i个符号为“-”;1≤i≤n。由于x[i]是2值的,所以在用回溯法解符号三角形问题时,可以用一棵完全二叉树来表示其解空间。在符号三角形的第一行的前i个符号x[1:i]确定后,就确定了一个由i*(i+1)/2个符号组成的符号三角形。下一步确定x[i+1]的值后,只要在前面已确定的符号三角形的右边加一条边,就可以扩展为x[1:i+1]所相应的符号三角形。(第一个符号有两种情况，分别以-开头或者以+开头)最终由x[1:n]所确定的符号三角形中包含的“＋”个数与“-”个数同为n×(n+1)/4。因此在回溯搜索过程中可用当前符号三角形所包含的“＋”个数与“ - ”个数均不超过n*(n+1)/4作为可行性约束,用于剪去不满足约束的子树。对于给定的n,当n×(n+1)/2为奇数时,显然不存在所包含的“＋”个数与“-”个数相同的符号三角形。这种情况可以通过简单的判断加以处理。

    sum记录当前已找到的“＋”个数与“一”个数相同的符号三角形数。

    在算法 backtrack 中,当i>n时,算法搜索至叶结点,得到一个新的“＋”个数与“ - ”个数相同的符号三角形,当前已找到符号三角形数sum增1。
    当i≤n时,当前扩展结点Z是解空间中的内部结点。该结点有x[i]=1和.x[i]=0共两个儿子结点。对当前扩展结点Z的每一个儿子结点,计算其相应的符号三角形中“＋”个数count与“-”个数,并以深度优先的方式递归地对可行子树搜索,或剪去不可行子树

    1. public class 符号三角形 {
    2.     static int n;//第一行的符号数
    3.     static int half;//n*（n+1）/4
    4.     static int count;//当前”+“个数
    5.     static int [][]p;//符号三角形矩阵
    6.     static long sum;//已找到的符号三角形数
    7.     public static long compute(int nn){
    8.         //初始化
    9.         n=nn;
    10.         count=0;
    11.         sum=0;
    12.         half=n*(n+1)/2;
    13.         if (half%2==1) return 0;//+ -符号为奇数时直接不成立
    14.         half=half/2;
    15.         p=new int[n+1][n+1];
    16.         //将三角形初始化全为 - 号
    17.         for (int i=0;i<=n;i++){
    18.             for (int j=0;j<=n;j++){
    19.                 p[i][j]=0;
    20.             }
    21.         }
    22.         backtrack(1);
    23.         return sum;
    24.     }
    25.     private static void backtrack(int t){//t遍历第一层的每一个点（一共n个）,每扫描一个点，确定一个三角型
    26.         if ((count>half)||((t*(t-1)/2)-count>half)) return;  //+号或者-号的数量大于一半，即不相等，则不成立
    27.         if (t>n) sum++;//直至扫描到最后一个点，三角形基本确定
    28.         else {
    29.             for (int i=0;i<2;i++){//两种情况，第一个点分别以 - 、 + 开头
    30.                 p[1][t]=i;//开头赋值（首先以“-”开头）
    31.                 count+=i;
    32.                 for (int j=2;j<=t;j++){//确定第一层第t点所确定的三角形（从第二层往下）
    33.                     p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];//0^1=0   1^0=0  1^1=1 0^0=1
    34.                     count+=p[j][t-j+1];
    35.                 }
    36.                 //第t个点的三角形确定，往下t+1个点
    37.                 backtrack(t+1);//递归，依次遍历所有的点
    38.                 //还原到最初始的状态，使第一个点实行第二种情况，以“+”开头
    39.                 for (int j=2;j<=t;j++){
    40.                     count-=p[j][t-j+1];
    41.                 }
    42.                 count-=i;
    43.             }
    44.         }
    45.     }
    46.  
    47. }

    N皇后问题

    在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。

    基本思想：用n元组x[1:n]表示n后问题的解。其中x[i]表示皇后 i 放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列,所以解向量中的x[i]互不相同。将n×n格棋盘看作二维方阵,其行号从上到下,列号从左到右依次编号1,2,…,n。从棋盘左上角到右下角的主对角线及其平行线（即斜率为-1的各斜线）上，2个下标值的差(行号 - 列号)值相等。因此,若2个皇后放置的位置分别是(i,j)和(k,l)，只要| i - k |=l j - l |成立,就表明2个皇后位于同一条斜线上。
    用回溯法解n后问题时,用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树。
    在算法 backtrack 中,当i≥n时,算法搜索至叶结点,得到一个新的n皇后互不攻击放置方案,当前已找到的可行方案数sum增1。
    当i≤n时,当前扩展结点Z是解空间中的内部结点。该结点有.x[i]=1,2，…,n,共n个儿子结点。对当前扩展结点Z的每一个儿子结点,由 place检查其可行性,并以深度优先的方式递归地对可行子树搜索或剪去不可行子树。

    1. public class Nqueen {
    2.     static int n;//皇后个数
    3.     static int []x;//当前解
    4.     static long sum;//当前已找到的可行方案数
    5.     public static long nqueen(int nn){
    6.         n=nn;
    7.         sum=0;
    8.         x=new int[n+1];
    9.         for (int i=0;i<=n;i++) x[i]=0;
    10.         backdigui(1);
    11.         return sum;
    12.     }
    13.     private static boolean place(int k){//可行性约束（不在同一对角线+不在同一列）
    14.         for (int j=1;j
    15.             /*
    16.             (j,x[j])与(k,x[k)               对角线         同一列
    17.              */
    18.             if ((Math.abs(k-j)==Math.abs(x[j]-x[k]))||(x[j]==x[k])) return false;
    19.         }
    20.         return true;
    21.     }
    22.     private static void backdigui(int t){
    23.         if (t>n) sum++;//已找到一个解决方案
    24.         else {
    25.             for (int i=1;i<=n;i++){
    26.                 x[t]=i;//皇后t的坐标为（t，i），共有n个i∈[1,n]
    27.                 if (place(t)) backdigui(t+1);
    28.                 /*
    29.                 除去约束后，皇后t的坐标为（t，i）{i有n种情况}的情况下，扩展节点变为t+1
    30.                 依次走下去（t+1坐标确定基础上，求t+2）直至到n
    31.                  */
    32.             }
    33.         }
    34.     }
    35.     private static void backNodigui(){
    36.         x[1]=0;
    37.         int k=1;//初始化
    38.         while (k>0){
    39.             x[k]+=1;//皇后k的坐标为（k,x[k]） {x[k]∈[1,n],皇后k的列从1到n依次遍历}
    40.             while ((x[k]<=n)&&!(place(k))) x[k]+=1;
    41.             /*
    42.             皇后k的列x[k]没u有到头，并且此列存在约束，则此列跳过不用，直到找到皇后k能使用的列
    43.             此语句结束，皇后k的位置(k,x[k])以确定，若皇后已全部找到，则返回一种办法。若皇后还没有找完，则进行下一个皇后
    44.              */
    45.             if (x[k]<=n){//列没到n
    46.                 if (k==n) sum++;//k=n表示n个皇后均扫描一次，表示找到了一种情况。
    47.                 else {
    48.                     k++;//进行下一个皇后，并且慈皇后的列从0开始遍历寻找
    49.                     x[k]=0;
    50.                 }
    51.             }else k--;//若x[k]>n，说明皇后k的列未找到，返回上一个皇后k-1，使其重新确定k-1的列
    52.         }
    53.     }
    54. }

    0-1背包问题

    在搜索解空间树时,只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索;否则将右子树剪去。设r是当前剩余物品价值总和;cp是当前价值; bestp是当前最优价值。当cp+r ≤bestp时,可剪去右子树。(表示背包容量能装下所有，无需拿出，故剪断右子树)

    计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。bound计算当前节点处的上界（最优值的上界）。仅当要进入右子树时才计算上界bound,以判断是否可将右子树剪去。进入左子树时不需计算上界,因为其上界与其父结点的上界相同。
     

    1. public class 背包01 {
    2.     static double c;//背包容量
    3.     static int n;//物品数
    4.     static double []w;//物品重量数组
    5.     static double []p;//物品价值数组
    6.     static double cw;//当前重量
    7.     static double cp;//当前价值
    8.     static double bestcp;//当前最有价值
    9.     static double []q;//单位重量价值
    10.  
    11.     public static double knapsack(double []p,double []w,double c){
    12.         //单位重量价值及其排序
    13.         for (int i=1;i<=n;i++){
    14.             q[i-1]=p[i-1]/w[i-1];
    15.         }
    16.         MergeSort.mergesort(q);
    17.         //回溯搜索
    18.         backtrack(1);
    19.         return bestcp;
    20.     }
    21.     private  static void backtrack(int i){
    22.         if (i>n){//到达叶结点
    23.             bestcp=cp;
    24.             return;
    25.         }
    26.         //搜索子树
    27.         if (cw+w[i]//背包还能装，进入左子树
    28.             cw+=w[i];
    29.             cp+=p[i];
    30.             backtrack(i+1);//进入下一层（直至将节点i所有的子树遍历完毕  ）
    31.             cw-=w[i];
    32.             cp-=p[i];//结点i的左子树遍历到底，将值返回节点i的初始值
    33.         }
    34.         if (bound(i+1)>bestcp){//bound(i)表示节点i的最大最优价值
    35.             //若最大最优价值大于当前最优价值，则可以继续优化，故进入右子树找最优值
    36.             //若最大最优价值等于最有价值，及已经最优化，无需进入右子树
    37.             backtrack(i+1);
    38.         }
    39.     }
    40.  
    41.     private static double bound(int i) {
    42.         //计算上界
    43.         double cleft=c-cw;
    44.         double bound=cp;
    45.         //以物品单位重量价值递减顺序装入物品
    46.         while (i<=n&&w[i]<=cleft){//装整数部分
    47.             cleft-=w[i];
    48.             bound+=p[i];
    49.             i++;
    50.         }
    51.         //装满背包，装部分
    52.         if (i<=n){
    53.             bound+=p[i]*cleft/w[i];
    54.         }
    55.         return bound;
    56.     }
    57. }

    旅行售货员问题

    问题:有n个城市，已知任两个城市之间的距离，求一条每个城市恰好经过一次的回路，使得总长度最小

    算法描述：
    旅行售货员问题的解空间是一颗排列数。

    在递归算法 backtrack中,当i=n时,当前扩展结点是排列树的叶结点的父结点。此是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在,则找到一条旅行售货员回路。此时,算法还需判断这条回路的费用是否优于当前已找到的最优回路的费用bestc。如果是,则必须更新当前最优值 bestc和当前最优解bestx。

    当i≤n时,当前扩展结点位于排列树的第i-1层。图G中存在从顶点x[i-1]到顶点a[i]的时,x[1:i]构成图G的一条路径,且当x[1:i]的费用小于当前最优值时算法进人排列树的第i层﹔否则,将剪去相应的子树。算法中用变量c记录当前路径x[1:i]的费用。

    1. public class 旅行售货员问题 {
    2.     static int n;//g的顶点数
    3.     static int []x;//当前解
    4.     static int []bestx;//当前最优解
    5.     static float bestc;//当前最优值
    6.     static float cc;//当前费用
    7.     static float [][]a;//图的邻接矩阵
    8.     public static float tsp(int []v){
    9.         for (int i=1;i<=n;i++) x[i]=i;
    10.         bestc=Float.MAX_VALUE;
    11.         bestx=v;
    12.         cc=0;
    13.         //搜索x[2,n]的全排列
    14.         backtrack(2);
    15.         return bestc;
    16.     }
    17.  
    18.     private static void backtrack(int i) {
    19.         if (i==n){//到达叶子节点，看点n-1~n与点n~1之间是否有通路，若有在比较大小进行更新
    20.             //a[x[n-1]][x[n]]存在通路
    21.             //cc+a[x[n-1]][x[n]]+a[x[n]][1]
    22.             if (a[x[n-1]][x[n]]1]1]][x[n]]+a[x[n]][1]
    23.                 for (int j=1;j<=n;j++){
    24.                     bestx[j]=x[j];//最优解排列更新
    25.                 }
    26.                 bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
    27.             }
    28.             else {//未遍历到叶子节点，看点i-1与之间是否有通路，且是在比较，确定是否更新
    29.                 for (int j=i;j<=n;j++){//点i与其他各点的连线
    30.                     //a[x[n-1]][x[j]]
    31.                     //cc+a[x[i-1]][x[i]]可以更新
    32.                     if (a[x[n-1]][x[j]]1]][x[i]]
    33.                         //搜索子树，j作为i节点的下一个节点进行搜索
    34.                         swap(x,i,j);//j作为新的节点，以i——j这条通路继续寻找
    35.                         cc+=a[x[i-1]][x[i]];//更新
    36.                         backtrack(i+1);//寻找j的通路
    37.                         cc-=a[x[i-1]][x[i]];
    38.                         swap(x,i,j);//还原返回结点i，遍历i的下一个通路寻找最优
    39.                     }
    40.                 }
    41.             }
    42.         }
    43.     }
    44.  
    45. }

    连续邮资问题

    假设国家发行了n种不同面值的邮票,并且规定每个信封上最多只允许贴m张邮票。连续邮资问题要求对于给定的n和m 的值,给出邮票面值的最佳设计,在1个信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。每张信封最多贴m张邮票，也就是说可能贴了m张，也可能贴了0张、1张等等。为了便于计算，我们可以把未贴满m张邮票看作贴了x张邮票和m-x张面值为0的邮票，从而构造一棵完全多叉树。若求所有可能的组合情况，解空间是(n+1)^m（即每张邮票均有n+1种选择）。
    例如,当n=5和m=4时,面值为(0,1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1～70。(故从这5中邮票中拿4张（可以相等），能构成的最大连续值，即从（0,1,3,11,15,32）中任取4张可以构成1~70任何一个数)

    解的约束条件是必须满足当前解的邮资可以构成增量为1的连续空间，所以在搜索至树中任一节点时，先判断该节点对应的部分解是否满足约束条件，也就是判断该节点是否包含问题的最优解，如果肯定不包含，则跳过对以该节点为根的子树的搜索，返回上一层的节点，从其他子节点寻找通向最优解的路径；否则，进入以该节点为根的子树，继续按照深度优先策略搜索。

    基本思想：

    读入邮票面值数n，每张信封最多贴的邮票数m
    读入邮票面值数组nums[]，除了正常面值，再加入一个值为0的面值
    循环求取区间最大值maxValue，maxValue初始设为0
    ① 从0张邮票开始搜索解空间，如果当前未达到叶节点，且过程值temp=temp+nums[i]未达到当前记录的区间最大值maxValue，则继续向下搜索
    ② 若超过了区间最大值maxValue，则当前面值不是可行解，计算下一个面值nums[i+1]。若循环结束，当前节点的所有面值都无法满足，则说明再往下搜索也不可能有可行解，这个时候回溯到上一节点
    ③ 若当前已搜索到叶节点，判断当前路径下的解temp是否满足比当前记录的区间最大值maxValue大1。若满足，则更新区间最大值maxValue；若不满足，回溯到上一节点
    重复步骤3直到没有满足当前区间最大值maxValue+1的可行解，则当前记录的maxValue就是区间最大值

    一颗颗子树的寻找，先寻找0000，在回溯到000找0001，在回溯到000找0003，依次。。。。然后在回溯到00找0010.。。。依次寻找完所有子树。

    1. public class 连续邮资问题 {
    2.     private static int n;// n表示邮票面值数，m表示每张信封最多贴的邮票数
    3.     private static int m;
    4.     private static int[] nums; // 邮票面值数组
    5.     private static boolean accFlag;// 当前解是否可行
    6.     private static int maxValue = 0;// 记录区间最大值
    7.     private static int temp = 0;// 搜索过程中的邮资
    8.  
    9.     public static void main(String[] args) {
    10.         Scanner sc = new Scanner(System.in);
    11.         while (true) {
    12.             n = sc.nextInt();
    13.             m = sc.nextInt();
    14.             nums = new int[n + 1];// 多一个是假设有面值为0的邮票
    15.             nums[0] = 0;
    16.             for (int i = 1; i < n + 1; i++) {
    17.                 nums[i] = sc.nextInt();
    18.             }
    19.             solution(n, m, nums);
    20.             System.out.println("maxValue=" + maxValue);
    21.         }
    22.     }
    23.  
    24.     public static void solution(int n, int m, int[] nums) {
    25.         while (true) {// 求解区间最大值，一直搜索，直到确定最大值
    26.             accFlag = false;// 每次都从0张邮票开始搜索解空间
    27.             search(0);// 当前求解的目标是判断是否存在比当前区间最大值大1的解
    28.             if (accFlag) { // 若存在,则更新连续区间最大值
    29.                 maxValue++;// 连续区间增量加1
    30.             } else {
    31.                 break;
    32.             }
    33.         }
    34.     }
    35.     public static void search(int t) {// t 当前邮票数量
    36.         //搜索解空间，找到比当前区间最大值大1的解
    37.         if (t == m) {// 叶节点，结束搜索
    38.             if (temp == maxValue + 1) {// 当前解可以将连续区间最大值加1
    39.                 accFlag = true;
    40.             }
    41.             // 此时已经是叶节点，若不是可行解，则需要回溯到t-1
    42.             return;
    43.         }
    44.         else{
    45.             // 未结束，继续向下搜索
    46.             // 遍历所有面值
    47.             for (int i = 0; i < nums.length; i++) {
    48.                 temp += nums[i];
    49.                 // 如果当前未达到叶节点，且过程值未达到当前记录的区间最大值，则继续向下搜索
    50.                 if (temp <= maxValue + 1) {
    51.                     search(t + 1);
    52.                 }
    53.                 // 若超过了区间最大值，则当前面值不是可行解，需要回溯，计算下一个面值
    54.                 temp -= nums[i];
    55.             }
    56.         }
    57.     }
    58. }

  • 相关阅读:
    java计算机毕业设计爱心公益网站设计与制作源码+系统+lw文档+mysql数据库+部署
    从零搭建开发脚手架 自定义HandlerMethodArgumentResolver-注解@JsonArg和实体CurrentUser
    CRM 自动化如何改善销售和客户服务？
    Java：get请求下字符串异常问题
    【从0到1开发一个网关】网关Mock功能的实现
    甘特图(Gantt Chart)绘制方法
    理想汽车×OceanBase：当造车新势力遇上数据库新势力
    基于SpringBoot+Vue的闲一品交易平台设计与实现
    安卓LeakCanary研究
    【C++】【Opencv】cv::GaussianBlur、cv::filter2D()函数详解和示例
  • 原文地址：https://blog.csdn.net/qq_39484271/article/details/127902118