java - 选择最佳运算符组合以找到目标数字

Question

我有一个操作数组和一个目标数。

操作可以是

+ 3
- 3
* 4
/ 2

我想知道通过使用这些操作，我能多接近目标数字。

我从 0 开始，我需要按该顺序遍历操作，我可以选择使用或不使用该操作。

所以如果目标数字是 13，我可以使用 + 3 和 * 4 得到 12，这是我能得到的最接近目标数字 13 的数字。

我想我需要计算所有可能的组合(我想计算次数因此是 2^n，其中 n 是操作数)。

我试过用 java 做这个

import java.util.*;

public class Instruction {
    public static void main(String[] args) {
        // create scanner
        Scanner sc = new Scanner(System.in);

        // number of instructions
        int N = sc.nextInt();

        // target number
        int K = sc.nextInt();

        //
        String[] instructions = new String[N];

        // N instructions follow
        for (int i=0; i<N; i++) {
            //
            instructions[i] = sc.nextLine();
        }

        //
        System.out.println(search(instructions, 0, N, 0, K, 0, K));
    }

    public static int search(String[] instructions, int index, int length, int progressSoFar, int targetNumber, int bestTarget, int bestDistance) {
        //
        for (int i=index; i<length; i++) {
            // get operator
            char operator = instructions[i].charAt(0);

            // get number
            int number = Integer.parseInt(instructions[i].split("\\s+")[1]);

            //
            if (operator == '+') {
                progressSoFar += number;
            } else if (operator == '*') {
                progressSoFar *= number;
            } else if (operator == '-') {
                progressSoFar -= number;
            } else if (operator == '/') {
                progressSoFar /= number;
            }

            //
            int distance = Math.abs(targetNumber - progressSoFar);

            // if the absolute distance between progress so far
            // and the target number is less than what we have
            // previously accomplished, we update best distance
            if (distance < bestDistance) {
                bestTarget = progressSoFar;
                bestDistance = distance;
            }

            //
            if (true) {
                return bestTarget;
            } else {
                return search(instructions, index + 1, length, progressSoFar, targetNumber, bestTarget, bestDistance);
            }
        }
    }
}

它还没有用，但我想我离解决我的问题更近了一点。我只是不知道如何结束我的递归。

但也许我不使用递归，而应该只列出所有组合。我只是不知道该怎么做。

例如，如果我有 3 个操作并且我想计算所有组合，我会得到 2^3 个组合

111
110
101
011
000
001
010
100

其中1表示使用了该操作，0表示未使用。

这样做应该相当简单，然后选择给出最佳结果的组合(最接近目标数字的数字)，但我不知道如何在 java 中执行此操作。

Answer 1

在伪代码中，您可以尝试暴力回溯，如:

// ops: list of ops that have not yet been tried out
// target: goal result
// currentOps: list of ops used so far
// best: reference to the best result achieved so far (can be altered; use
//     an int[1], for example)
// opsForBest: list of ops used to achieve best result so far
test(ops, target, currentOps, best, opsForBest)
      if ops is now empty,
         current = evaluate(currentOps)
         if current is closer to target than best,
            best = current
            opsForBest = a copy of currentOps
      otherwise, 
         // try including next op
         with the next operator in ops,
            test(opsAfterNext, target, 
                currentOps concatenated with next, best, opsForBest)
         // try *not* including next op
         test(opsAfterNext, target, currentOps, best, opsForBest)

保证找到最佳答案。但是，它会一次又一次地重复许多操作。您可以通过避免重复计算来节省一些时间，这可以使用“这个子表达式如何求值”的缓存来实现。当您包含缓存时，您就进入了“动态编程”领域(= 在以后的计算中重用早期的结果)。

---

编辑:添加更面向对象的变体

变体返回最好的结果，并避免使用那个best[] array-of-one。需要使用带有字段 ops 和 result 的辅助类 Answer。

// ops: list of ops that have not yet been tried out
// target: goal result
// currentOps: list of ops used so far
Answer test(ops, target, currentOps, opsForBest)
      if ops is now empty,
         return new Answer(currentOps, evaluate(currentOps))
      otherwise, 
         // try including next op
         with the next operator in ops,
            Answer withOp = test(opsAfterNext, target, 
                currentOps concatenated with next, best, opsForBest)
         // try *not* including next op
         Answer withoutOp = test(opsAfterNext, target, 
                currentOps, best, opsForBest)
         if withOp.result closer to target than withoutOp.target,
            return withOp
         else
            return withoutOp