一个递归问题，请教大家

[woodenwang]

@woodenwang 终于改出来了，现在能打印所有可行投币方案，包括最优解。但是，我还是不很懂……

public class Main {
  
    private static int res = 0;
    private static int minRes = 0;
    private static int cnt = 0;
  
    public static void main(String[] args) {
      
        System.out.print("Target: ");
        Scanner in = new Scanner(System.in);
        int target = in.nextInt();
        // Start with 10 öre
        findCoin(1,1,target, "");
        // Reset res
        res = 0;
        // Start with 5 öre
        findCoin(1,2,target, "");
        System.out.println("Minimal result = " + minRes);
    }

    /**
     * 1 => 10 öre, 2 => 5 öre
     * 1 * 3 * 3 = 9; 1 + 4 + 4 = 9;
     * @param current
     * @param type
     * @param target
     */
    private static void findCoin(int current, int type, int target, String s) {
      
        if(type == 1) {
            current *= 3;
            res += 10;
            s = s + "10->";
        }
        if (type ==2) {
            current += 4;
            res += 5;
            s = s + "5->";
        }
        if (current == target) {
            if(res < minRes || minRes == 0) {
                minRes = res;      
            }
            cnt ++;
            System.out.println("Solution " + cnt + ": " + s);
        }
        if (current < target) {
            findCoin(current, 1, target, s);
            res -= 10;
            findCoin(current, 2, target, s);
            res -= 5;
        }
    }
}

这个版本能够输出所有解，是因为s 在递归调用的参数列表中，当递归回退的时候，其实自动已经将s重置到之前的状态，所以不需要再手动对s做状态重置，但目前你的代码只实现的输出所有解，你可以参看我上一个解法，实现输出最优解。

 

[woodenwang]

总结出来就是：
以递归实现的回溯算法，如果表示当前状态的变量处在递归调用的方法参数中，则由于递归调用的特性，决定了其自然而然的回溯特征，无需人工干预，每次调用返回时，所有方法参数自动回溯至上一个状态，但如果表示状态的变量是一个全局变量，不在递归调用的方法参数列表中，则必须人工对状态进行回退，以完成回溯的过程。

 

[gongbao]

[FONT=楷体]“以递归实现的回溯算法，如果表示当前状态的变量处在递归调用的方法参数中，则由于递归调用的特性，决定了其自然而然的回溯特征，无需人工干预，每次调用返回时，所有方法参数自动回溯至上一个状态，但如果表示状态的变量是一个全局变量，不在递归调用的方法参数列表中，则必须人工对状态进行回退，以完成回溯的过程。”
[/FONT]
----- 这句话我需要花很多时间体会，再次感谢！！

总结出来就是：
以递归实现的回溯算法，如果表示当前状态的变量处在递归调用的方法参数中，则由于递归调用的特性，决定了其自然而然的回溯特征，无需人工干预，每次调用返回时，所有方法参数自动回溯至上一个状态，但如果表示状态的变量是一个全局变量，不在递归调用的方法参数列表中，则必须人工对状态进行回退，以完成回溯的过程。

 

[gongbao]

    private static int coins(int target) {
        Queue<State> q = new LinkedList<>();
        State s = new State(1, 0, target);
        q.add(s);
        int min = Integer.MAX_VALUE;
        while(!q.isEmpty()) {
            State current = q.peek();
            if (current.display==s.target&&current.coins<min)
              min = current.coins;  
            if(current.display * 3 <= s.target) {
                int newDisplay = current.display * 3;
                int newCoins = current.coins + 10;
                q.offer(new State(newDisplay, newCoins, s.target));
            }
            if(current.display + 4 <= s.target) {
                int newDisplay = current.display + 4;
                int newCoins = current.coins + 5;              
                q.offer(new State(newDisplay, newCoins, s.target));
            }
          
            q.poll();
        }
      
        return min;
    }

帮你改对以后的，不过你原来的那个里面错误比较多，我没办法一一给你指出，你可以对比一下我改完的代码

这个改过的是深度优先，但不是回溯法？
我那天特意问老师，他说回溯法只能与广度优先结合使用，不能与深度优先结合。

 

[woodenwang]

这个改过的是深度优先，但不是回溯法？
我那天特意问老师，他说回溯法只能与广度优先结合使用，不能与深度优先结合。

这个改过的是广度优先，我估计你可能听反了，应该是回溯法只能和深度优先相结合，不能与广度优先结合。

 

[woodenwang]

回溯搜索是深度优先搜索（DFS）的一种，回溯法通俗的将其采用的思想是“一直向下走，走不通就掉头”，类似于树的先序遍历。dfs和回溯法其主要的区别是：回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。

 

[woodenwang]

BFS广度优先，则是采取逐层扩展的方式搜索，首先扩展根节点，将所有的可能的扩展都记录下来，然后对于第一层扩展的节点再逐一扩展，得到所有第二步的结果，因此，广度搜素首先得到的解，一定就是扩展次数最少的解（不一定是最优解，因为可能都扩展5步，但每步的代价不一样 （本题就是这样，每步的代价可能是5,可能是10)，如果每步扩展的代价是一样的（你上次提的另外一个黑球白球移动的就是），则最先找到的就是最优解）。通常来说，BFS 可以更快地搜索到最优解，但是其需要记录大量的搜素状态空间，可以理解为以空间换取时间，而DFS则不需要记录太多的状态，但在极端情况下，可能要将整个搜索空间遍历完，才能找到最优解，所以往往出解的时间要更长。当然如果是从图遍历的角度来说，BFS 和 DFS 的时间复杂度都是 O （n^2)， 但实际的搜索过程，并不总需要完成所有的遍历，这也就使得两者在搜索最优解的时间上有所差异。

 

[woodenwang]

广度优先是逐层扩展，所以不存在回溯，也就是说扩展过了，就不会再回头了。可以用一个简单的例子来帮助理解，假设你站在一个黑屋子中间，手拿一个只能照亮身边一米范围的灯，要找到一个宝箱，广度优先，就是你先把身边第一层的8个格子都各走一步，如果没找到宝箱，就再往外走一层，把第2层的16个格子全部走一遍，如果还没找到，就再往外扩展走一层，所以不存在回头的问题，而深度优先，就是你先认定一个方向，一直走下去，走到屋子边界上走不了了，则往来路退一步，再看有没有其他的路可以走，这个退一步的过程，就是回溯。

 

[dennistan2009]

就是说DFS肯定是回溯，BFS肯定不是回溯了。

 

[dennistan2009]

好像有点不对，DFS是每条路径必须要走通，回溯是有一条路径，并且找到猎物就退出了。

 

[gongbao]

这个改过的是广度优先，我估计你可能听反了，应该是回溯法只能和深度优先相结合，不能与广度优先结合。

可能是我记反了……

 

[woodenwang]

好像有点不对，DFS是每条路径必须要走通，回溯是有一条路径，并且找到猎物就退出了。

DFS 是深度优先搜索， 回溯是深度优先搜索的最常用的实现方式，“每条路径必须要走通” 这个是使用深度优先搜索，完成图的遍历. "找到一个猎物就退出”，是使用回溯法找一个可行解。

 

[woodenwang]

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

 

[gongbao]

这个版本的关键错误在于回溯过程中，没有将状态回到之前的位置，由于steps 栈并不在递归调用的参数列表中，所以每次回溯的时候，都必须pop以回到之前的状态
参看修改后的代码如下：

    public static int result = 0;
    public static int min_result = 0;
    private static Stack<String> steps = new Stack<>();
    private static List<String> bestSteps = new ArrayList<String>();
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int goal = in.nextInt();
        //first insert 10 coins
        findCoin(1,1,goal);
        //let result be to zero
        result = 0;
        //first insert 5 coins
        findCoin(1,2,goal);
        System.out.println(min_result);
        //output best steps here
        for(int i = 0; i < bestSteps.size(); i ++) {
            System.out.print(bestSteps.get(i));
        }
      
    }
  

  
    public static void findCoin(int current, int type,int goal){
        if (type==1){
            current = current * 3;
            result += 10;
            steps.push("10->");
        }        
        if (type==2){
         current += 4;
         result += 5;
         steps.push("5->");
        }
        if (current == goal){
            /* output each solution from here
            System.out.print("coins"+result+"with steps");
            for(int i = 0; i < steps.size(); i ++) {
                System.out.print(steps.elementAt(i));
            }
            System.out.println();
            */
            if (result<min_result||min_result==0){
                min_result = result;
                //recording current best solution
                bestSteps = new ArrayList<String>();
                bestSteps.addAll(steps);
            }
        }
      
        if (current < goal){
            findCoin(current,1,goal);
            result -= 10;
            //steps is not in the parameter list, during backtracking, always back the previous state
            steps.pop();
            findCoin(current,2,goal);
            result -= 5;
            //steps is not in the parameter list, during backtracking, always back the previous state
            steps.pop();
        }
    }

这个厉害，完全正确，连总币值，步骤，最优解全都有！
百思不得其解，我当初试来试去，也把steps.push(), steps.pop()放到对应的4个位置，可就是不对呢？可惜我把代码都删除了，不然一定要对比一下。当初有个致命的错误是把steps.pop()放在main函数那两个findCoin(1,1,goal);和findCoin(1,2,goal)之间，还曾经在那个位置尝试过将steps清空。

 

[gongbao]

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。

而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

迄今为止，还是觉得回溯，广度优先，深度优先最难。这两天练习到哈希表和二叉树，没有几个难。

 

[dennistan2009]

我个人觉得，把算法思想体现到具体代码，这一步是最难的。
思想不难，代码不难，把两者结合起来，这是一个过程，需要练习的。

 

[gongbao]

我个人觉得，把算法思想体现到具体代码，这一步是最难的。
思想不难，代码不难，把两者结合起来，这是一个过程，需要练习的。

算法思想不难理解，实现成代码implementation难

 

[idogicat]

109开始往下拆，

1. 能被3整除 ---> 除3
---> 减4

2. 不能被3整除 ---> 减4

递归至1.

取最优解。

这个不一定啊，比如9，最优解是1+4+4 （10元），而不是1x3x3（20元）。按上述算法，会得出后者。感觉应该找出各种路径，然后选最优解？

 

[dennistan2009]

早选了八百遍了，白头发都选出来了啦，还要选啊。

 

[gongbao]

早选了八百遍了，白头发都选出来了啦，还要选啊。

就像给你选妃一样，你就有动力了