如何为最少元素达标或超标的动态规划算法设置初始数字？

原代码的问题 #

原代码仅能计算恰好等于目标值的最少元素数量，无法处理「超过目标值」的场景，同时不支持指定必须包含某个初始元素的需求。

处理指定初始元素的思路 #

如果必须选择某个初始数字（比如示例中的3），可以按以下逻辑处理：

• 先从目标值中减去该初始数字，得到新的目标值：new_target = target - initial_num
• 在原数组中移除一个该初始数字（避免重复使用同一个元素，若数组中有多个相同元素则只需移除一个）
• 计算在剩余数组中，达到或超过new_target所需的最少元素数量，最后加上1（即已选的初始数字）

修改后的完整代码 #

def find_least_numbers_to_exceed_target(numbers, target):
    # 计算达到或超过target的最少元素数
    max_possible = target + max(numbers) if numbers else 0
    dp = [float('inf')] * (max_possible + 1)
    dp[0] = 0
    
    for num in numbers:
        for i in range(max_possible, num - 1, -1):
            dp[i] = min(dp[i], dp[i - num] + 1)
    
    # 找到大于等于target的最小dp值
    min_count = float('inf')
    for i in range(target, max_possible + 1):
        if dp[i] < min_count:
            min_count = dp[i]
    return min_count if min_count != float('inf') else -1  # -1表示无法达到

def find_with_initial_number(numbers, target, initial_num):
    # 检查初始数字是否存在于数组中
    if initial_num not in numbers:
        return -1  # 不存在则无法满足要求
    
    # 移除一个初始数字
    new_numbers = numbers.copy()
    new_numbers.remove(initial_num)
    
    # 计算剩余需要达到的目标
    new_target = target - initial_num
    # 剩余目标可能为负，说明初始数字已经超过目标，直接返回1
    if new_target <= 0:
        return 1
    
    # 计算剩余数组的最少元素数，加1（初始数字）
    rest_count = find_least_numbers_to_exceed_target(new_numbers, new_target)
    return rest_count + 1 if rest_count != -1 else -1

# 示例使用
numbers = [4, 3, 4, 1, 2]
target = 10
initial_num = 3

result = find_with_initial_number(numbers, target, initial_num)
print(f"必须包含{initial_num}时，达到或超过{target}所需最少元素数为：{result}")

示例解释 #

对于你的示例：

• 初始数字选3，剩余目标为10-3=7
• 剩余数组为[4,4,1,2]，达到或超过7的最少元素是2（两个4，和为8≥7）
• 总元素数为2+1=3，符合你说的3+4+4=11≥10的情况

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