I have been trying to find an efficient solution for following programming problem but haven't found a satisfying solution yet:

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.

I have two solutions so far that find through recursion/dynamic programming the highest number that is achievable by transferring n segments. The recursive solution in Java looks like this:

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 stores each digit of the given number. maxTransfer stores the amount of given transfers. neededTransfers is precalculated and stores the amount of transfers you need to get from one digit to another (For example, to get from 4 to 5 you would need neededTransfers[5][4] transfers). segmentQuantity stores how many segments each digit has. Before the recursion starts, the number of given segments is calculated because our new number should have the same amount of segments. As long as we haven't exceeded the limit of maximum transfers, haven't used more segments than possible and it is still possible to use all segments the recursion checks if the it there is a solution if the current number is changed to the highest (9) then the next highest (8) and so on. If a solution is found it is printed and the program is finished.
While this works for smaller numbers, it is to inefficient for longer numbers. Does anybody have an idea how this could be solved instead?

CodePudding user response：

As you have that recursiv solution made better with dynamic programming, try avoiding futile choices:
- when all transfers are used up, the only suffix possible is the given one
- raise the lower bound on segments to (number.length-i)*2
  (or decrement all segment counts (including *7) by 2)
- given digit is a lower bound for the first digit changed

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

True. But currently, you are just limiting removals.
When tallying both additions & removals, you can limit both:

    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