选择运营商的最佳组合以查找目标编号

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[]数组。需要使用Answer带有字段ops和的辅助类result。

// 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