时间戳

首页 > 解决方案 > 如何将解决方案从递归方法调用传递给调用方法？（回溯算法）

java - 如何将解决方案从递归方法调用传递给调用方法？（回溯算法）

问题描述

我正在尝试实现一种回溯算法来平衡秤上的权重。这是给大学的，所以我必须使用给定的权重（0、2、7、20、70、200、700）。重量可以多次放置在秤上以匹配输入。例如：input(80) -> result(20, 20, 20, 20) 或 input(16) -> result(7,7,2)。我必须使用回溯和递归。

如果提案错误，我很难理解如何进行回溯。我只能后退一步，但如果正确的解决方案需要后退两步，我的算法就会失败。

所以我的方法 isInvalid() 正在检查所有配重的总和是否高于输入。如果是这样，它将删除最后一个重量。我想这是我的问题。对于 input(16) 它产生 (7,7,2) --> 正确。但是对于 input(21) 它永远不会完成，因为它尝试添加 20，然后尝试添加 7。然后它将超过 21 并删除 7，但它永远不会删除 20。

/* 这是我的回溯算法 */

  public Proposal calc(Proposal proposal) {
    Proposal result;
    if(proposal.isInvalid()) return null;
    if(proposal.isSolution()) return proposal;

    for (int i : proposal.possibleNextSteps()) {
       Proposal newProposal = new Proposal(proposal.getWeight(), proposal.getCounterWeights());
       newProposal.apply(i);
       result = calc(newProposal);
       if (result != null) return result;
    }
    return null;
}

/* 这是类提案（仅需要的部分）*/

public class Proposal {
private int weight;
private ArrayList<Integer> counterWeights;
private static Integer[] weights = {0, 2, 7, 20, 70, 200};

public Proposal(int weight, ArrayList<Integer> counterWeights) {
    this.weight = weight;
    this.counterWeights = counterWeights;
    Arrays.sort(weights, Collections.reverseOrder());
}

public boolean isInvalid() {
    if(counterWeights.stream().mapToInt(i -> i.intValue()).sum() > weight) {
        counterWeights.remove(counterWeights.size()-1);
        return true;
    }
    return false;

}


public boolean isSolution() {
    return counterWeights.stream().mapToInt(value -> value).sum() == weight;
}

public Integer[] possibleNextSteps() {
    return  weights;
}

public void apply(int option) {
    this.counterWeights.add(option);
}

}

我究竟做错了什么？而且，这是反转我的权重数组的正确方法吗？

谢谢！

编辑： 我尝试了一些不同的东西。我改变了这个：

Proposal newProposal = new Proposal(proposal.getWeight()- proposal.getSum(), new ArrayList<>());

和这个：

 public boolean isInvalid() {  
  return counterWeights.stream().mapToInt(value -> value).sum() > weight;
}

所以现在如果我在调试模式下一步一步地遵循它，它几乎是在做我想要它做的事情，但它不会将我的递归解决方案传递给我以前的解决方案，所以它们不会加起来成为最终解决方案. 所以基本上我把问题分解成更小的问题（一旦我找到合适的权重，我会用总权重和我已经找到的解决方案之间的差异递归调用该方法）。但是如何将解决方案传递给调用方法？

标签： javarecursionbacktracking

解决方案

在以下实现中，解决方案是一个系数数组。索引 i 处的系数是位置 i 处的权重在解中出现的次数。

请注意，您可以有多个具有相同总权重的解决方案，此实现提供了所有解决方案。很容易将其更改为仅返回找到的第一个解决方案。

递归方法void solve(int weight, int n, int total)尝试索引n总权重不大于目标权重的所有整数。

public class Solver {
    private final int[] weights;
    private int[] current;
    private final List<int[]> solutions = new ArrayList<>();

    public Solver(int...weights) {
        this.weights = weights;
    }

    public int[][] solve(int weight) {
        current = new int[weights.length];
        solutions.clear();
        solve(weight, 0, 0);
        return solutions.toArray(new int[solutions.size()][]);
    }

    public void printSolution(int[] solution) {
        int total = 0;
        for (int i = 0; i < solution.length; ++i) {
            for (int j = 0; j < solution[i]; ++j) {
                System.out.print(weights[i] + " ");
                total += weights[i];
            }
        }
        System.out.println(" total: " + total);
        System.out.println();
    }

    private void solve(int weight, int n, int total) {
        if (n >= current.length) {
            if (total == weight) {
                solutions.add(current.clone());
            }
        } else {
            solve(weight, n+1, total);
            while (total < weight) {
                ++current[n];
                total += weights[n];
                solve(weight, n+1, total);
            }
            current[n] = 0;
        }
    }
}

推荐阅读