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

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中实现。

- Jamgreen

---

好玩！这让我想起了https://en.wikipedia.org/wiki/24_Game。 - JakeRobb

好头痛啊！ :) 真想在这里提供帮助。 - Yassin Hajaj

你不需要将“length”传递出去。Java数组总是可以告诉你它们的长度。例如：int[] a = new int[5]; System.out.println(""+a.length); 输出结果为5。 - tucuxi

我建议你选择其他的操作组合。你提供的一组仅产生七个不同的结果，其中三个是另外三个的逆运算。将第二个操作改为-1，这样你会得到一个更好的示例。 - Prune

相关至少，可能类似：https://dev59.com/hXvaa4cB1Zd3GeqPJu8K#21463659 - Marco13

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

- tucuxi

---

一旦退出，best 中的值是正确的，并且 opsForBest 包含生成它的运算符序列。当然，您可以使其返回 best（那么您就不需要将其传递）。编辑变量。 - tucuxi

@tucuxi 我认为你要找的词是摊销，而不是缓存本身。 - SGM1

@SGM1我实在看不懂在上下文中如何用“摊销”来代替“缓存”。能否解释一下？ - tucuxi

哎呀，我搞错了，记忆化才是正确的术语，是从j_random那里得到的。 - SGM1

Answer 2

动态规划

如果目标值为t，列表中有n个操作，通过组合它们的某些子序列可以创建的最大绝对值为k，并且作为除法操作数出现的所有值的绝对值乘积为d，则有一个简单的O(dkn)时间和空间动态规划算法，确定是否可能使用前j个操作的某个子集计算出值i，并将此答案（单个位）存储在dp[i][j]中：

dp[i][j] = dp[i][j-1] || dp[invOp(i, j)][j-1]

invOp(i, j) 函数计算值为 i 的第 j 个操作的逆运算。请注意，如果第 j 个操作是乘以 x，而 i 不可被 x 整除，则认为该操作没有逆运算，术语 dp[invOp(i, j)][j-1] 被视为 false。所有其他操作都有唯一的逆运算。

为避免浮点代码的精度损失问题，首先将原始目标值 t 以及加减运算的所有操作数乘以 d。这确保我们遇到的任何除法运算 / x 都只会应用于已知可被 x 整除的值。我们将基本上使用 1/d 的整数倍进行工作。

由于某些操作（即减法和除法）需要解决更高的目标值的子问题，因此我们通常无法以自下而上的方式计算 dp[i][j]。相反，我们可以使用自上而下递归的记忆化，从（缩放后的）目标值 t*d 开始，在每个方向上以 1 的步长向外扩展。

C++ 实现

我已经在C++中实现了这个https://ideone.com/hU1Rpq。 "有趣"的部分是canReach(i, j); 在此之前的函数只是处理记忆化表的管道。使用标准输入指定目标值，然后是以空格分隔的操作列表，其中运算符紧接着其操作数值，例如：

10 +8 +11 /2

或者

10 +4000 +5500 /1000

第二个例子应该给出与第一个相同的答案（9.5），但似乎已经接近 ideone（和我的）内存限制，尽管可以通过使用 long long int 替换 int 并使用 2 位表格代替每个条目上浪费一个完整字节的 _m [] [] [] 来扩展它。

指数最坏时间和空间复杂度

请注意，在一般情况下，dk 或仅 k 本身可能会随着输入大小呈指数增长：例如，如果有一个加法，然后是 n-1 个乘法操作，每个操作都涉及一个大于 1 的数字。通过不同的 DP 可以很容易地精确计算 k，它只需查找所有 1 <= i <= n 的第一个 i 操作可达到的最大和最小数字，但我们真正需要的只是一个上限，而且很容易获得一个（有点宽松）：简单地丢弃所有乘法操作数的符号，将所有 - 操作转换为 + 操作，然后执行 所有 乘法和加法操作（即忽略除法）。

还有其他可以应用的优化，例如通过任何公共因子进行除法。

- j_random_hacker

---

这怎么处理与目标最接近的结果，而不是精确匹配呢？ - tucuxi

@tucuxi：第116行的for循环从精确目标开始查找，并继续尝试距离目标越来越远的值（上下两个方向），直到找到一个为止。（它必须终止，因为最终会尝试值0。） - j_random_hacker

@tucuxi：另外请参见我的答案：“相反，我们可以使用自顶向下递归的记忆化，从（缩放后的）目标值t*d开始，向每个方向以1的步长向外计算。”最后，我故意选择了目标=10，最近解=9.5的示例，以显示找到非精确最近解 :) - j_random_hacker

Answer 3

这是一个Java 8的例子，使用记忆化技术。我想知道退火算法是否可以应用...

public class Tester {

    public static interface Operation {
        public int doOperation(int cur);
    }

    static Operation ops[] = { // lambdas for the opertions
            (x -> x + 3),
            (x -> x - 3),
            (x -> x * 4),
            (x -> x / 2), 
    };

    private static int getTarget(){
        return 2;
    }

    public static void main (String args[]){
        int map[];
        int val = 0;
        int MAX_BITMASK = (1 << ops.length) - 1;//means ops.length < 31 [int overflow]
        map = new int[MAX_BITMASK];
        map[0] = val;

        final int target = getTarget();// To get rid of dead code warning

        int closest = val, delta = target < 0? -target: target;
        int bestSeq = 0;

        if (0 == target) {
            System.out.println("Winning sequence: Do nothing");
        }

        int lastBitMask = 0, opIndex = 0;
        int i = 0;
        for (i = 1; i < MAX_BITMASK; i++){// brute force algo
            val = map[i & lastBitMask]; // get prev memoized value
            val = ops[opIndex].doOperation(val); // compute
            map[i] = val; //add new memo

            //the rest just logic to find the closest
            // except the last part
            int d = val - target;
            d = d < 0? -d: d;
            if (d < delta) {
                bestSeq = i;
                closest = val;
                delta = d;
            }
            if (val == target){ // no point to continue
                break;
            }

            //advance memo mask 0b001 to 0b011 to 0b111, etc.
            // as well as the computing operation.
            if ((i & (i + 1)) == 0){ // check for 2^n -1
                lastBitMask = (lastBitMask << 1) + 1;
                opIndex++;
            }
        }
        System.out.println("Winning sequence: " + bestSeq);
        System.out.println("Closest to \'" + target + "\' is: " + closest);
    }

}

值得注意的是，“获胜序列”是使用和未使用的位表示（以十进制显示），正如OP在问题中所做的那样。

对于那些来自Java 7的人，这就是我参考的lambda：Lambda Expressionsin GUI Applications。因此，如果您受到7的限制，您仍然可以轻松地使其工作。

- SGM1