java - 给定多个范围选择数字组合以达到给定的总和

Question

给定范围，即 (1-6)、(3-6)、(2-5) 和要达到的总和是 13。我应该能够从每个范围中选择数字，使它们的总和为 13。

示例输出：（3,5,5），（4,4,5）等

我正在用java代码尝试这个，但无法弄清楚确切的实现。我需要在这个范围内生成随机数并检查这些数字的总和。这里有无限循环的危险。你能帮我解决这个问题吗？

public static void main(String[] args) {
    int rangeStart1 = 1;
    int rangeEnd1 = 6;

    int rangeStart2 = 3;
    int rangeEnd2 = 6;

    int rangeStart3 = 2;
    int rangeEnd3 = 5;

    int sum = 13;
    int obtainedSum = 0;
    int randomNum1 = 0;
    int randomNum2 = 0;
    int randomNum3 = 0;
    while (obtainedSum != sum) {
        randomNum1 = (int)((Math.random() * (rangeEnd1 - rangeStart1)) + rangeStart1);
        randomNum2 = (int)((Math.random() * (rangeEnd2 - rangeStart2)) + rangeStart2);
        randomNum3 = (int)((Math.random() * (rangeEnd3 - rangeStart3)) + rangeStart3);
        obtainedSum = obtainedSum + randomNum1 + randomNum2 + randomNum3;
    }

    System.out.println(obtainedSum);
    System.out.println(randomNum1);
    System.out.println(randomNum2);
    System.out.println(randomNum3);
}

标签： javaalgorithm

Answer 1

要从与给定总和匹配的数值数组中找到给定的数字排列，您可以使用蛮力算法来查找可能的组合。为此，您可以在构建中使用深度优先搜索，方法是一次从每个数组中选择一个数字来构建路径。

对于您的示例输入{ [1-6], [3-6], [2-5] }（包括结尾），有效路径可以是1 > 3 > 2（每个数组中的第一个数字）。通过递归，您可以评估所有可能的路径并找到与给定总和匹配的路径。

首先，一些定义使用 Java 记录语法来避免不必要的样板代码。如果需要，您可以将这些类反向移植到较低的 Java 版本。

// input range to pick numbers from
public record Range(int startInclusive, int endInclusive) {

    @Override
    public String toString() {
        return "[" + startInclusive + "," + endInclusive + "]";
    }
}

// a node in the graph contains the picked number and the range
// that this number has been picked from
public record Node(Range range, int number) {
    
    @Override
    public String toString() {
        return number + " from " + range.toString();
    }
}

// connection of multiple nodes in a graph
public record Path(Collection<Node> nodes) {

    public static Path EMPTY = new Path(Collections.emptyList());

    // sum of all current nodes
    public int sum() {
        int sum = 0;
        for (Node s : nodes()) {
            sum += s.number;
        }
        return sum;
    }

    // copy of this path with the node added
    public Path with(Node node) {
        List<Node> nodes = new ArrayList<>(nodes());
        nodes.add(node);
        return new Path(nodes);
    }
}

现在，aPathContext存储递归期间使用的必要信息。

public class PathContext {

    private final Range[] ranges;
    private final int sum;

    // resulting paths that match the sum
    private final Collection<Path> paths = new ArrayList<>();
    // find all matches or just one (latter is faster)
    private final boolean skipAfterMatch = false;

    public PathContext(Collection<Range> ranges, int sum) {
        this.ranges = ranges.toArray(new Range[0]);
        this.sum = sum;
    }

    // if the path a valid solution, add it the the results
    public void validatePath(Path path) {
        if (path.sum() == sum) {
            paths.add(path);
        }
    }

    public Range[] getRanges() {
        return ranges;
    }

    public Collection<Path> getPaths() {
        return Collections.unmodifiableCollection(paths);
    }

    public int getSum() {
        return sum;
    }
    
    public boolean abortSearch() {
        return skipAfterMatch && !paths.isEmpty();
    }
}

现在终于，dfs（深度优先搜索）：

public static void dfs(PathContext ctx, int rangeIdx, Path path) {
    // if we have no more ranges to pick from, validate if the sum matches
    if (rangeIdx >= ctx.getRanges().length) {
        ctx.validatePath(path);
    } else {
        // get the next range
        Range next = ctx.getRanges()[rangeIdx];

        // traverse trough all numbers in the range, end inclusive
        for (int i = next.startInclusive; i <= next.endInclusive; i++) {
            // generate a new node and path
            Node node = new Node(next, i);
            Path newPath = path.with(node);

            // recurse with the next range
            dfs(ctx, rangeIdx + 1, newPath);

            // check if the search can be aborted (if only one match is needed)
            if (ctx.abortSearch()) {
                break;
            }
        }
    }
}

然后，您可以dfs使用您的示例数据进行调用：

public static void main(String[] args) {
    Range range1 = new Range(1, 6);
    Range range2 = new Range(3, 6);
    Range range3 = new Range(2, 5);
    List<Range> ranges = List.of(range1, range2, range3);

    PathContext ctx = new PathContext(ranges, 13);
    // start from index 0 (the first range)
    dfs(ctx, 0, Path.EMPTY);

    // output logging
    System.out.println("total sum: " + ctx.getSum());
    for (Path path : ctx.getPaths()) {

        for (Node node : path.nodes()) {
            System.out.println(node);
        }
        System.out.println();
    }
}

结果输出是：

total sum: 13
2 from [1,6]
6 from [3,6]
5 from [2,5]

3 from [1,6]
5 from [3,6]
5 from [2,5]

3 from [1,6]
6 from [3,6]
4 from [2,5]

4 from [1,6]
4 from [3,6]
5 from [2,5]

4 from [1,6]
5 from [3,6]
4 from [2,5]

4 from [1,6]
6 from [3,6]
3 from [2,5]

5 from [1,6]
3 from [3,6]
5 from [2,5]

5 from [1,6]
4 from [3,6]
4 from [2,5]

5 from [1,6]
5 from [3,6]
3 from [2,5]

5 from [1,6]
6 from [3,6]
2 from [2,5]

6 from [1,6]
3 from [3,6]
4 from [2,5]

6 from [1,6]
4 from [3,6]
3 from [2,5]

6 from [1,6]
5 from [3,6]
2 from [2,5]