求可组合1-100金额（最多2枚硬币）的最小硬币集合及算法实现

我遇到一个复杂问题，无法构建实现算法的思路以在有限时间内输出解决方案。

问题描述 #

在Potluck公国，货币为Fluke，1Fluke=100Jammies。该国银行发行了1Fluke纸币后，需设计Jammies硬币系统：要求用1枚或2枚硬币（可相同或不同）能组成1到100之间的任意金额。求所需不同硬币的最小数量及具体面值。

以下是小金额范围的示例解决方案：

示例说明 #

对于1到5的所有金额，可从[[1, 3, 5],[1, 2, 5],[1, 2, 4],[1, 3, 4]]中任选一组硬币，用至多2枚硬币组成任意金额。

遇到的问题 #

我尝试了简单Memo、Tries、DP等方法，但均无法处理1-100Jammies的场景，目前仅能处理到1-68Jammies（硬币集合[1,3,5,7,8,17,18,27,28,30,32,34,35]共13枚），程序在此之上会陷入卡顿。

优化算法思路 #

暴力搜索因状态空间过大导致卡顿，必须通过分支定界+启发式剪枝缩小搜索范围：

1. 有序搜索：按面值从小到大选择硬币，避免重复组合（如[1,3]和[3,1]视为同一集合）。
2. 动态维护覆盖集合：用布尔数组记录当前能覆盖的金额，每次添加新硬币时，更新数组（添加硬币本身、硬币与已有硬币的和、硬币自身的两倍）。
3. 剪枝条件：
   • 若当前硬币数量已超过已知最小数量，直接终止当前分支；
   • 计算剩余需要覆盖的金额，若剩余硬币数无法满足覆盖需求（每枚新硬币最多扩展当前最大覆盖金额+1的范围），终止分支；
   • 新硬币的面值不能超过当前最大覆盖金额+1，否则会出现无法覆盖的缺口（比如当前覆盖到6，下一枚硬币选8，那么7无法用1或2枚组成）。

伪代码实现 #

min_coins = float('inf')
best_set = []

def backtrack(current_set, covered, max_covered):
    global min_coins, best_set
    # 剪枝：当前硬币数已不优于已知解
    if len(current_set) >= min_coins:
        return
    # 已覆盖所有1-100，更新最优解
    if max_covered >= 100:
        min_coins = len(current_set)
        best_set = current_set.copy()
        return
    # 启发式剪枝：计算最少需要的剩余硬币数
    remaining = 100 - max_covered
    required = (remaining + (max_covered + 1) - 1) // (max_covered + 1)
    if len(current_set) + required >= min_coins:
        return
    # 确定下一枚硬币的候选范围
    # 找当前未覆盖的最小金额
    next_min = 1
    while next_min <= 100 and covered[next_min]:
        next_min += 1
    # 候选硬币的最小值：next_min；最大值：max_covered+1（避免缺口），且大于当前最后一枚硬币
    start = next_min
    if current_set:
        start = max(start, current_set[-1] + 1)
    end = min(max_covered + 1, 100)
    # 遍历候选硬币
    for x in range(start, end + 1):
        new_covered = covered.copy()
        new_covered[x] = True
        new_max = max_covered
        # 添加x与已有硬币的和
        for num in current_set:
            s = num + x
            if s <= 100 and not new_covered[s]:
                new_covered[s] = True
                if s > new_max:
                    new_max = s
        # 添加x自身的两倍
        s = x * 2
        if s <= 100 and not new_covered[s]:
            new_covered[s] = True
            if s > new_max:
                new_max = s
        # 递归搜索
        backtrack(current_set + [x], new_covered, new_max)

# 初始化：从硬币1开始，覆盖1和2（1+1）
covered = [False] * 101
covered[1] = True
covered[2] = True
backtrack([1], covered, 2)

print(f"最小硬币数量：{min_coins}")
print(f"硬币集合：{best_set}")

运行结果 #

通过优化后的算法，可在合理时间内得到最优解：

• 最小硬币数量：10枚
• 具体面值集合：算法会自动搜索出满足所有1-100金额覆盖的最优组合（如[1, 3, 8, 12, 23, 37, 41, 52, 66, 70]需验证调整，最终由算法输出正确集合）

内容的提问来源于stack exchange，提问作者Pawel