c++ - 从火柴棒制作数字的算法

Question

我编写了一个程序来解决this problem来自 ACM。

Matchsticks are ideal tools to represent numbers. A common way to represent the ten decimal digits with matchsticks is the following:

This is identical to how numbers are displayed on an ordinary alarm clock. With a given number of matchsticks you can generate a wide range of numbers. We are wondering what the smallest and largest numbers are that can be created by using all your matchsticks.

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with an integer n (2 ≤ n ≤ 100): the number of matchsticks you have. Output

Per testcase:

One line with the smallest and largest numbers you can create, separated by a single space. Both numbers should be positive and contain no leading zeroes. Sample Input

4 3 6 7 15 Sample Output

7 7 6 111 8 711 108 7111111

问题是解决 100 根火柴棒的速度太慢了。搜索树太大，无法对其进行暴力破解。

前 10 个结果如下:

2: 1 1

3: 7 7

4:4 11

5: 2 71

6: 6 111

7: 8 711

8: 10 1111

9: 18 7111

10: 22 11111

最大值的模式很简单，但我没有找到最小值的捷径。有人可以建议更好的方法来解决这个问题吗？这是我使用的代码:

    #include <iostream>
    #include <string>
    using namespace std;

    #define MAX 20 //should be 100

    //match[i] contains number of matches needed to form i
    int match[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    string mi[MAX+1], ma[MAX+1];
    char curr[MAX+1] = "";

    //compare numbers saved as strings
    int mycmp(string s1, string s2)
    {
        int n = (int)s1.length();
        int m = (int)s2.length();
        if (n != m)
            return n - m;
        else
            return s1.compare(s2);
    }

    //i is the current digit, used are the number of matchsticks so far
    void fill(int i, int used)
    {
        //check for smaller and bigger values
        if (mycmp(curr, mi[used]) < 0) mi[used] = curr;
        if (mycmp(curr, ma[used]) > 0) ma[used] = curr;

        //recurse further, don't start numbers with a zero
        for (int a = i ? '0' : '1'; a <= '9'; a++) {
            int next = used + match[a-'0'];
            if (next <= MAX) {
                curr[i] = a;
                curr[i+1] = '\0';
                fill(i + 1, next);
            }
        }
    }

    int main()
    {
        //initialise 
        for (int i = 0; i <= MAX; i++) {
            mi[i] = string(MAX, '9');
            ma[i] = "0";
        }

        //precalculate the values
        fill(0, 0);

        int n;
        cin >> n;

        //print those that were asked
        while (n--) {
            int num;
            cin >> num;
            cout << mi[num] << " " << ma[num] << endl;
        }

        return 0;
    }

编辑:我最终使用了动态规划解决方案。我之前用 dp 试过，但我在摆弄一个二维状态数组。这里的解决方案要好得多。谢谢!

Answer 1

您可以使用动态规划解决方案。

假设你有 n 个匹配项，并且你知道如何解决所有 n-k 匹配项的问题(最小数量)，其中 k 取对应的所有值到每个数字使用的匹配数(2 代表 1，5 代表 3，等等)

然后递归地导出解决方案。假设您的数字以 1 结尾(在最低位)，那么最好的解决方案是编写 (best solution with n-2 matches) 1。假设你以 2 结尾，最好的解决方案是 (best solution with n-5 matches) 2。等等 ;最终你可以比较这十个数字，然后选出最好的一个。

所以现在，您所要做的就是递归地为所有小于您的输入的 n 设计最佳解决方案。

编辑:如果您以直接的方式实现此算法，您最终会得到指数级的复杂度。这里的技巧是要注意，如果您的核心函数 MinimumGivenNMatches 只接受一个参数，n。因此，您最终会多次使用相同的值调用它。

要使复杂度呈线性，您只需使用辅助数组记住(即记住)每个 n 的解决方案。