通过传输 n 段来最大化 7 段显示器上的数字

Question

我一直在尝试为以下编程问题找到有效的解决方案，但尚未找到令人满意的解决方案：

You are given a number displayed in the 7-segment system. What's the maximum number you can get, when you are allowed to transfer n segments. In the transfer, you take one segment of a digit, and place it in the empty space of a digit. This can happen within one digit or between two different digits. The number of digits should not change.

到目前为止，我有两个解决方案，它们通过 recursion/dynamic 编程找到通过传输 n 段可实现的最大数量。 Java 中的递归解如下所示：

public static int[] number = {1,2,3,4};
public static int maxTransfers = 3;

public static int[] segmentQuantity = {6,2,5,5,4,5,6,3,7,6};
public static int[][] neededTransfers = {
        {0,0,1,1,1,1,1,0,1,1},
        {4,0,4,3,2,4,5,1,5,4},
        {2,1,0,1,2,2,2,1,2,2},
        {2,0,1,0,1,1,2,0,2,1},
        {3,0,3,2,0,2,3,1,3,2},
        {2,1,2,1,1,0,1,1,2,1},
        {1,1,1,1,1,0,0,1,1,1},
        {3,0,3,2,2,3,4,0,4,3},
        {0,0,0,0,0,0,0,0,0,0},
        {1,0,1,0,0,0,1,0,1,0}};

public static void main(String[] args)
{
    int existingSegments = 0;
    for (int i = 0; i < number.length; i++)
    {
         existingSegments += segmentQuantity[number[i]];
    }
    rekursiv(0, maxTransfers, existingSegments, "");
}

public static boolean rekursiv(int i, int transfersLeft, int segmentsLeft, String usedNumbers)
{
    if (transfersLeft < 0 || segmentsLeft  < 0 || segmentsLeft > (number.length-i)*7)
    {
        return false;
    }
    if (i == number.length)
    {
        System.out.println(usedNumbers);
        return true;
    }
    return 
    rekursiv(i+1,transfersLeft-neededTransfers[9][number[i]],segmentsLeft-segmentQuantity[9], usedNumbers+9) ||
    rekursiv(i+1,transfersLeft-neededTransfers[8][number[i]],segmentsLeft-segmentQuantity[8], usedNumbers+8) ||
    rekursiv(i+1,transfersLeft-neededTransfers[7][number[i]],segmentsLeft-segmentQuantity[7], usedNumbers+7) ||
    rekursiv(i+1,transfersLeft-neededTransfers[6][number[i]],segmentsLeft-segmentQuantity[6], usedNumbers+6) ||
    rekursiv(i+1,transfersLeft-neededTransfers[5][number[i]],segmentsLeft-segmentQuantity[5], usedNumbers+5) ||
    rekursiv(i+1,transfersLeft-neededTransfers[4][number[i]],segmentsLeft-segmentQuantity[4], usedNumbers+4) ||
    rekursiv(i+1,transfersLeft-neededTransfers[3][number[i]],segmentsLeft-segmentQuantity[3], usedNumbers+3) ||
    rekursiv(i+1,transfersLeft-neededTransfers[2][number[i]],segmentsLeft-segmentQuantity[2], usedNumbers+2) ||
    rekursiv(i+1,transfersLeft-neededTransfers[1][number[i]],segmentsLeft-segmentQuantity[1], usedNumbers+1) ||
    rekursiv(i+1,transfersLeft-neededTransfers[0][number[i]],segmentsLeft-segmentQuantity[0], usedNumbers+0);
}

number 存储给定数字的每个数字。 maxTransfer 存储给定的转账金额。 neededTransfers 是预先计算好的，它存储了从一个数字到另一个数字所需的转账金额（例如，要从 4 到 5，您需要 neededTransfers[5][4] 次转账）。 segmentQuantity 存储每个数字有多少段。在递归开始之前，计算给定段的数量，因为我们的新数字应该具有相同数量的段。只要我们没有超过最大传输的限制，没有使用超过可能的段数并且仍然可以使用所有段递归检查如果当前数字更改为最高是否有解决方案(9) 然后是下一个最高的 (8) 等等。如果找到解决方案，则将其打印出来，程序结束。
虽然这适用于较小的数字，但对于较长的数字来说效率低下。有人知道如何解决这个问题吗？

Answer 1

因为你有 recursiv solution made better with dynamic programming，尽量避免无用的选择：
- 当所有传输都用完时，唯一可能的后缀是给定的
- 将段的下限提高到 (number.length-i)*2
（或将所有段数（包括 *7）减 2）
- 给定数字是第一个更改数字的下限

If I would also include the segments that need to be removed, I would count everything twice.

没错。但目前，您只是限制移除。
在计算添加和删除时，您可以同时限制：

    static String digits;

    /** Greedily tries substituting digits from most significant to least,
     *  from 9 to 0. */
    static boolean 
    recursiveGreedy(int i, int additions, int removals, int segments, String prefix)
    {
        if (additions < 0 || removals < 0
            || segments < (number.length-i)*2 || segments > (number.length-i)*7)
            return false;
        if (i == number.length) {  // -> segments 0!
            System.out.println(prefix);
            return true;
        }
        final int givenDigit = number[i];
        if (0 == additions && 0 == removals)
            return recursiveGreedy(i+1, 0, 0,
                segments - segmentsActive[givenDigit], prefix+givenDigit);
        for (int d = 10, least = // i==0 ||
            digits.startsWith(prefix) ? givenDigit : 0 ; least <= --d ; )
            if (recursiveGreedy(i+1, additions - neededTransfers[d][givenDigit],
                                     removals  - neededTransfers[givenDigit][d],
                                     segments-segmentsActive[d], prefix+d))
                return true;
        return false;
    }
        // where given digit is ...
        // 0, you don't need to try 6, 3, or 2 because 9 ...
        // 1, you don't need to try 2 because 5 ...
        // 5, you don't need to try 6 because 9 ...
        //    ... has the same number of additions & removals

通过传输 n 段来最大化 7 段显示器上的数字

Maximizing number on 7-segment display by transfering n segments

algorithm

recursion

dynamic-programming