我一直在嘗試為以下編程問題找到一個有效的解決方案，但還沒有找到令人滿意的解決方案：
您將獲得一個顯示在 7 段系統中的數字。當您被允許轉移 n 段時，您可以獲得的最大數量是多少。在傳輸中，你取一個數字的一??段，并將它放在一個數字的空白處。這可能發生在一個數字內或兩個不同數字之間。位數不應改變。
到目前為止，我有兩個解決方案，通過遞回/動態編程找到通過傳輸 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)，依此類推。如果找到解決方案，則會列印并完成程式。
雖然這適用于較小的數字，但對于較長的數字效率低下。有誰知道如何解決這個問題？
uj5u.com熱心網友回復：
正如你所擁有的那樣recursiv solution made better with dynamic programming，盡量避免徒勞的選擇：
- 當所有傳輸都用完時，唯一可能的后綴是給定的
- 將段的下限提高到(number.length-i)*2
? （或將所有段計數（包括 *7）減 2）
- 給定digit 是更改的第一個數字的下限
如果我還包括需要洗掉的部分，我會將所有內容計算兩次。
真的。但目前，您只是限制洗掉。
在計算添加和洗掉時，您可以同時限制兩者：
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/460998.html
上一篇：JS、遞回、函式堆疊示例，難懂