【回溯法】使用回溯算法解决多个数和的问题（java）

【回溯法】使用回溯算法解决多个数和的问题（java）

算法设计与分析实验八：回溯法

1.主观题 (10分)

实验八：使用回溯算法解决多个数和的问题（Sum It Up）（完成实验报告三、四、五、六的内容）

一、实验目的

       练习使用回溯算法解决实际问题（使用Java语言实现）。

二、实验内容

【问题描述】

给出一个n,k,再给出n个数中，输出所有的可能使几个数的和等于k的组合，输入的n和k的值都为0时退出。

三、 程序代码

（1）SumItUp

package sumItUp;

import java.util.Scanner;

public class SumItUp {
    public int sum0;
    public int maxSum;
    public int nowSum;
    private int[] num;//=new int[7];//先改一下方便调试
    public int numberOfNum;
    public int numSum;
    private boolean[] picking;//=new boolean[7];
    public void input(){
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入想要得到的相加值：");
        numSum=scanner.nextInt();
        System.out.println("请输入数字总数目：");
        numberOfNum=scanner.nextInt();
        num=new int[numberOfNum];
        picking=new boolean[numberOfNum];
        System.out.println("请输入对应的数字：");
        for (int i=0;inumberOfNum-1)//已经到达叶子结点
        {
           return;
        }
        if (nowSum+num[t]==numSum){
            picking[t]=true;
            nowSum+=num[t];
            outputData(picking);
            nowSum-=num[t];
            picking[t]=false;
            backtrack(t+1);
        }
        if(nowSum+num[t]numSum) //如果满足限制条件则搜索右子树
        {
            picking[t]=false;
            backtrack(t+1);
        }

    }

}

（2）Test

package sumItUp;

import java.util.Scanner;

public class Test {
    public static void main(String[] arg){
        //4 7       6 4 3 2 2 1 1
        //5 4       3 2 1 1
        //400 13    12 50 50 50 50 50 50 25 25 25 25 25 25
        int test=1;
        Scanner scanner=new Scanner(System.in);
        while (test==1){
            System.out.println("开始测试！");
            SumItUp sumItUp=new SumItUp();
            sumItUp.input();
            sumItUp.backtrack(0);
            System.out.println("请输入是否继续测试（继续测试请输入1停止测试输入0）");
            test=scanner.nextInt();
        }
        System.out.println("停止测试！");
    }
}

四、 实验结果（含程序运行截图）

五、 出现问题及解决方法

出现的问题有很多，有一个问题到现在也没有解决，那就是如何使一种结果只输出一次，我想的是将每个结果都保留然后进行循环比较相同的结果，相同的结果只输出一个，但是这样做我认为比较复杂而且我想的方法时间复杂度比较高不是很划算，所以也想知道有没有更好的方法。

在写程序中遇到的问题有许多，通过一遍遍遍历挨个去解决。

（1）与老师上课讲的回溯法相比来说不同的是要输出所有可行解而不是最优解

所以不能跟例子代码一样等寻找到根节点在输出解，而是找到一个可行解就输出一个，找到可行解输出后要退回去再进行右子树的遍历。

if (nowSum+num[t]==numSum){
   picking[t]=true;
   nowSum+=num[t];
   outputData(picking);//输出此时的可行解
   nowSum-=num[t];//回退到上一个节点
   picking[t]=false;//转到右子树
   backtrack(t+1);//进行右子树的遍历
}

一开始的代码只是单纯的进行输出可行解没有进行节点的回退就直接进行右子树的遍历，所以在debug后发现这个问题了，改正后的代码如上。

（2）对于循环右子树的条件一开始定义的是当当前的和加上下个数字的值大于要求的和值，

if(nowSum+num[t]>numSum)
{
   picking[t]=false;
   backtrack(t+1);
}

发现这样没有办法在左子树遍历回来后的回退节点：backtrack(t+1);nowSum-=num[t];节点回退后只能判断当前和值加上下一个数字的值是否大于要求的和值，发现如果不大于就不能进行右子树的遍历，才明白例子中的代码这个bound方法的作用。修改后右子树遍历的条件为剩下的数字和值相加大于要求的和值。

if(bound(t+1)>numSum) //如果满足限制条件则搜索右子树
{
   picking[t]=false;
   backtrack(t+1);
}

这样就可以进行在左子树遍历后进行右子树的遍历前提是右子树的最大和大于要求的和值，有可能找到可行解。

（3）输出可行解的时候只能是遍历picking这个布尔类型的数组，当值为true时对应的输出num数组再此位置的数字，而且由于要输出加号那么需要提前判断最后一个true的位置，最后一个数字对应的不输出加号。

for (int i=0;i    if (picking[i]==true) {
       lastTrueLocation=i;//记录最后一个true的位置
   }
}
for (int j=0;j    if (picking[j]==true){
       if(j!=lastTrueLocation)
       {
           System.out.print(num[j]+"+");//不是最后位置的true则输出数字跟加号
       }else {
           System.out.print(num[j]);//最后位置的只输出数字
       }
   }
}

（3）由于我们是找到可行解就输出，则例子中的当输入的数字正好是要求的和值不需要特地拿出来当作一种情况，一开始当成了特殊情况，后来在debug过程中发现了这个冗余的代码。如下：

for (int i=0;i< sumItUp.numberOfNum;i++){
   sumItUp.maxSum+=sumItUp.num[i];
}
if (sumItUp.maxSum==sumItUp.numSum){
   System.out.println("和值为输入数字相加！");
}else {
   sumItUp.backtrack(0);
}

其实是不需要的。

六、 实验心得

本次实验的回溯法还是主要参考老师给的例程代码，要是自己写回溯法的递归函数我认为是有难度的，我发现debug是读懂一个算法或者说程序的最好的办法，本来我在课上听得还有些不理解，比如遍历右子树时的那个bound函数的作用，但是在自己debug的时候就全明白了。