编写一个算法来决定是否可以用一组其他数字和特定运算符到达目标数字？

Question

我正在努力学习更多关于算法设计的知识，并且我给自己设置了一个挑战:创建一个简单的游戏，向用户呈现一个数字数组、一个目标数字和一系列运算符(加、减、乘、除，也许还有平方根等等)。我需要做的是决定是否可以使用数组中的可用数字来生成目标数字。

我有点困惑，不知道从哪里开始。在游戏的不同回合中，不同的运营商可能是可用的，例如+, -, *, and /、+ and -、只有+ and *或除+之外的所有运营商等。

我说我需要为每个运算符组合(不管有多少个，20个或更多)有效地需要一个单独的算法，这是正确的吗？如果是这样，我是否需要遍历网格中的每个数字，对数组中的每个其他数字执行每个可用的运算符？这看起来太混乱了，但我真的不确定还有其他选择。这个选项在多个操作中也不遵循任何特定的路径(例如，如果我想执行7，那么如果这些是数组中唯一可用的数字，我可能会执行12 + 5 - 10 )。

有谁能给我一些建议，告诉我从哪里开始解决这类问题？

Answer 1

您正面临一个更普遍的Partition Problem问题，那就是NP-Complete。

分区问题是:给定n号，将它们分成两个(不同的)组A和B，以便sum(A) = sum(B)。现在，很容易看出，如果你有一个+，-运算符和目标数字0的问题-这基本上是相同的问题，并且从分区问题立即减少到你的问题。

从这里我们可以得出结论，你的问题也是NP-Hard的，并且对于你的问题，没有已知的多项式解。

替代方案包括：

1. Brute Force (正如@Sayakiss)
2. Depending在运算符上所建议的那样-您也许能够使用一些在这里也可以使用的techniques.
3. For Partition Problem there is pseudo-polynomial Dynamic Programming solution，，至少在某些情况下是这样。

抱歉，如果这是个坏消息，-but至少你不会寻找(大多数计算机科学家认为)不存在的东西

Answer 2

1. 枚举所有可能的表达式。对于数字1、2、3以及运算符+和-，您可以get:1+2+3,1+2-3,1-2+3,1-2-3.
2. Evaluate所有可能的表达式。

Answer 3

这是一个来自programcreek的Java solution。

public static boolean isReachable(ArrayList<Integer> list, int target) {
    if (list == null || list.size() == 0)
        return false;

    int i = 0;
    int j = list.size() - 1;

    ArrayList<Integer> results = getResults(list, i, j, target);

    for (int num : results) {
        if (num == target) {
            return true;
        }
    }

    return false;
}

public static ArrayList<Integer> getResults(ArrayList<Integer> list,
        int left, int right, int target) {
    ArrayList<Integer> result = new ArrayList<Integer>();

    if (left > right) {
        return result;
    } else if (left == right) {
        result.add(list.get(left));
        return result;
    }

    for (int i = left; i < right; i++) {

        ArrayList<Integer> result1 = getResults(list, left, i, target);
        ArrayList<Integer> result2 = getResults(list, i + 1, right, target);

        for (int x : result1) {
            for (int y : result2) {
                result.add(x + y);
                result.add(x - y);
                result.add(x * y);
                if (y != 0)
                    result.add(x / y);
            }
        }
    }

    return result;
}