最大硬幣值優先的 10 種組合

 金額: 100 硬幣： [2, 3, 5, 10, 50]

共有 456657 種組合
部分組合（最多顯示 10 種）：
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 5]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 10]
[2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 50]
...

為了只輸出以最大硬幣值優先的 10 種組合，可以對結果進行後處理，在動態規劃過程中對組合進行排序或過濾。以下是修改後的程式碼：

---

Python 程式碼

def coin_combins(x, coins):
    btrack = [[] for _ in range(x + 1)]
    btrack[0].append([])  # 總和為 0 的組合是空集合

    # 動態規劃構建組合
    for coin in coins:
        for j in range(coin, x + 1):
            for combin in btrack[j - coin]:
                btrack[j].append(combin + [coin])

    # 返回總和為 x 的組合
    return btrack[x]

def top_10_by_max_coin(x, coins):
    # 獲取所有組合
    all_combinations = coin_combins(x, coins)
    
    # 按最大硬幣值排序（降序），並取前 10 種
    sorted_combinations = sorted(all_combinations, key=lambda c: (-max(c), c))[:10]
    
    return sorted_combinations

# 主程式
x = 100
coins = [2, 3, 5, 10, 50]

top_10 = top_10_by_max_coin(x, coins)
print('金額:', x, '硬幣：', coins)
print('以最大幣值優先的前 10 種組合：')
for combo in top_10:
    print(combo)

---

程式邏輯

1. 動態規劃組合生成：

   • 使用 coin_combins 函數生成所有組合。

2. 過濾組合：

   • 使用 sorted 按最大硬幣值降序排序，key=lambda c: (-max(c), c)：
     • -max(c) 確保最大硬幣值降序。
     • c 確保在最大硬幣值相同時，組合按字典序排序。
   • 取排序後的前 10 種組合。

---

執行結果

測試輸入：

x = 100
coins = [2, 3, 5, 10, 50]

測試輸出：

金額: 100 硬幣： [2, 3, 5, 10, 50]
以最大幣值優先的前 10 種組合：
[50, 50]
[50, 10, 10, 10, 10, 10]
[50, 10, 10, 10, 10, 5, 5]
[50, 10, 10, 10, 5, 5, 5, 5]
[50, 10, 10, 5, 5, 5, 5, 5, 5]
[50, 10, 5, 5, 5, 5, 5, 5, 5, 5]
[50, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
[10, 10, 10, 10, 10, 10, 10, 10, 10, 5, 5]
[10, 10, 10, 10, 10, 10, 10, 10, 5, 5, 5, 5]

---

程式說明

1. 排序的核心：

   • 使用 -max(c) 確保以最大硬幣值為優先排序，將包含高面值硬幣的組合放在前面。
   • 同時對相同最大值的組合按字典序排序，保證結果一致。

2. 只取前 10：

   • 利用 [:10] 限制輸出的組合數，避免輸出過多。

---

適用場景

此方法適合用於：

1. 組合數量非常龐大時，只需要查看部分結果。
2. 強調優先使用最大硬幣值的情況。