6

我正在努力学习更多关于算法设计的知识，我给自己设定了一个挑战，即创建一个简单的游戏，向用户展示一组数字、一个目标数字和一系列运算符（加、减、乘、除，也许是平方根等等）。我需要做的是决定是否可以使用数组中的可用数字来制作该目标数字。

我有点不知道从哪里开始。在游戏的不同回合中，可能会用到不同的算子，例如+, -, *, and /, + and -, only+ and *或 all except+等。

我是否正确地说我需要为每个运算符组合（无论有多少，20 个或其他）有效地需要一个单独的算法？如果是这样，那么我是否需要遍历网格中的每个数字，对数组中的每个其他数字执行每个可用的运算符？这似乎过于混乱，但我不确定还有什么其他选择。此选项也不会通过多个操作遵循任何特定路径（例如，如果我想 make ，如果这些是数组中我唯一可用的数字7，我可能会这样做）。12 + 5 - 10

谁能给我一些关于从哪里开始解决这类问题的指示？

4

3 回答 3

7

You are facing a more generalized problem of the Partition Problem, which is NP-Complete.

The Partition Problem is: Given n numbers, split them into two (distinct) groups A and B such that sum(A) = sum(B). Now, it is easy to see that if you have a problem with +,- operators and target number 0 - this is basically the same problem, and there is an immidiate reduction from Partition Problem to your problem.

From this we can conclude your problem is NP-Hard as well, and there is no known polynomial solution for your problem.

Alternatives are:

  1. Brute Force (As suggested by @Sayakiss)
  2. Depending on the operators - you might be able to use some branch and bound techniques.
  3. For Partition Problem there is pseudo-polynomial Dynamic Programming solution, that might be utilized in here as well, at least for some of the cases.

Sorry if it's bad news -but at least you won't be looking for something that (most computer scientists believe) is not there

于 2013-05-15T13:11:02.260 回答
0

  1. 枚举所有可能的表达式。对于数字 1,2,3 和运算符 + 和 - ，可以得到：1+2+3,1+2-3,1-2+3,1-2-3。

  2. 评估所有可能的表达式。

于 2013-05-15T13:02:43.650 回答
-1

这是来自 programcreek的 Java解决方案。

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;
}
于 2016-04-15T20:13:13.640 回答