如何优化从可重复正整数集合凑目标值的最少元素算法？

给定正整数集合和目标值m，需要找到用最少元素（元素可重复使用）相加得到m的组合。比如集合{1,2}、目标值7时，最优解是2+2+2+1（共4个元素）。但下面的算法运行极慢，计算目标值13时都有明显延迟，求优化方案或更高效算法。

原代码如下：

import itertools

def can_make_sum(target, numbers_to_use):
    numbers = [False] * (target + 1)  # numbers[i] stores False if i cannot be made with numbers_to_use, or a tuple
    # storing its factors with the smallest multiplier
    for number in numbers_to_use:
        multiplier = 1
        while True:
            product = multiplier * number
            if product > target:
                break
            if not numbers[product]:  # If the value is False
                numbers[product] = (number, multiplier)
            else:
                if numbers[product][1] > multiplier:  # only replace the multiplier if it is smaller than the previous
                    numbers[product] = (number, multiplier)  # multiplier, so it is the shortest way to make that number

            multiplier += 1

    usable_numbers = []
    for product in numbers:
        if product != False:
            for _ in range(product[1]):
                usable_numbers.append(product[0])

    answer = []  # Final answer

    for i in range(1, len(numbers)):
        subsets = list(itertools.combinations(usable_numbers, i))  # All subsets of the usable numbers with length i
        for subset in subsets:
            total = sum(subset)
            if total == target:  # This is the smallest subset
                for num in subset:
                    for _ in range(numbers[num][1]):
                        answer.append(numbers[num][0])

                return answer

print(can_make_sum(13, {1, 2, 3}))

原算法慢的核心原因 #

• 指数级组合生成：itertools.combinations会生成所有长度为i的组合，当usable_numbers元素数量大时，组合数会爆炸式增长，完全没必要。
• 冗余预处理：usable_numbers把每个数的倍数拆成多个重复元素，进一步放大了组合数规模，属于无效操作。

更高效的解法：动态规划（无限背包变种） #

这是典型的「最少硬币问题」，属于无限背包范畴，时间复杂度为O(m*n)（m是目标值，n是集合元素个数），效率远超原算法。

思路说明 #

1. DP数组定义：dp[i]表示凑出值i所需的最少元素个数，初始时dp[0] = 0（凑0需要0个元素），其余设为无穷大（表示暂时无法凑出）。
2. 状态转移：对每个目标值i（从1到m），遍历集合中的每个数num，如果i >= num且dp[i - num] + 1 < dp[i]，则更新dp[i] = dp[i - num] + 1，同时记录该步使用的num用于后续回溯。
3. 回溯找组合：从目标值m反向遍历，找到每一步使用的元素，直到回到0，反转结果即可得到具体组合。

实现代码 #

def min_elements_sum(target, numbers):
    # 过滤掉大于目标值的无效元素
    numbers = [num for num in numbers if num <= target and num > 0]
    if not numbers:
        return None  # 无法凑出目标值
    
    # 初始化dp数组和回溯记录数组
    dp = [float('inf')] * (target + 1)
    dp[0] = 0
    prev_num = [None] * (target + 1)
    
    for i in range(1, target + 1):
        for num in numbers:
            if i >= num and dp[i - num] + 1 < dp[i]:
                dp[i] = dp[i - num] + 1
                prev_num[i] = num
    
    if dp[target] == float('inf'):
        return None  # 无法凑出目标值
    
    # 回溯生成具体组合
    result = []
    current = target
    while current > 0:
        num = prev_num[current]
        result.append(num)
        current -= num
    
    return result

# 测试示例
print(min_elements_sum(7, {1, 2}))  # 输出 [2,2,2,1] 或等价最少元素组合
print(min_elements_sum(13, {1, 2, 3}))  # 输出 [3,3,3,3,1] 或 [3,3,3,2,2] 等（均为5个元素）

效率优势 #

对于目标值13，仅需13*3=39次计算，完全不会有延迟；即使目标值达到1000，也只需要千级别的计算量，性能碾压原算法。

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