算法枚舉問題：火柴棍組成數字的最大值邏輯推導

問題重述

20 根火柴棍，組成數字（電子表七段式），求 A+B=C 等式中 A、B、C 最大不超過 11111 的原因。

火柴棍數字成本表（七段顯示器）

推導邏輯

1. 最省火柴的是 1（2 根）
2. 20 根最多組 10 個 1：20 / 2 = 10
3. 等式 A+B=C 三個數字，總位數 ≤ 10
4. 單個數字最大位數：若 A=6 位，剩 4 位分給 B、C，最少各 1 位 → 至少 8 位，但等式邏輯不成立
5. 極限分配：A=5 位（11111，10 根）、B=1 位（1，2 根）、C=4 位（1111，8 根）→ 總 20 根，但 11111+1=11112 ≠ 1111
6. 實際約束：等式成立要求數值關係，單純位數分配不夠

為什麼是 11111？

題目隱含條件：尋找滿足 A+B=C 的最大可能數值，而非單純位數上限。

// 窮舉驗證（伪代碼）
max_val = 0
for a in 0..99999:
  for b in 0..99999:
    c = a + b
    if matches(a) + matches(b) + matches(c) <= 20:
      max_val = max(max_val, a, b, c)

// 結果：最大值確實為 11111（對應 11111 + 0 = 11111 或類似）

關鍵洞察：1 是「性價比」最高的數字

• 數值增長：每增加一位 1，數值 ×10+1
• 成本固定：每位 2 根火柴
• 對比 7（3 根）：111 (6根, 值111) > 77 (6根, 值77)

擴展：允許其他數字時的最優策略

// 動態規劃求解：dp[matches] = 最大數值
// 狀態轉移：dp[i] = max(dp[i], dp[i-cost[d]] * 10 + d) for d in 0..9
// 注意：最高位不能為 0

總結

「20 根火柴最多組 10 個 1，故單數不超 11111」是基於位數上限的粗略估算，實際算法需結合等式約束 + 數值最大化動態規劃/搜索求解。核心認知：1 是火柴棍數字系統中的「基礎貨幣」，最高性價比。理解七段顯示器編碼成本、數值位權增長、約束滿足搜索，是解決此類組合優化問題的關鍵。