满足或超过目标值的最少元素数求解及代码修正求助

原代码问题 #

以下代码意图实现“找出满足或超过目标值所需的最少元素数量”，但未符合实际需求规则：

def find_least_numbers_to_exceed_target(numbers, target):
    dp = [float(-1)] * (target + 1)
    dp[0] = 0    
    for num in numbers:
        for i in range(target, num - 1, -1):
            dp[i] = min(dp[i], dp[i - num] + 1)

    return dp[target]

numbers = [70, 86, 19]
initial = 20
target = 100 - initial

result = find_least_numbers_to_exceed_target(numbers, target)
print(f"The least number of elements needed to achieve {target} or exceed it is {result}")

实际需求规则 #

• 初始值为给定的initial，每次只能从列表中选取小于当前总和的元素
• 每个元素仅能使用一次
• 累加后需达到或超过目标值target，求所需的最少元素数量

示例 #

例1：列表[70,86,19]，initial=20，target=80。初始总和20，仅能选19，累加后为39，无更小元素可用，无法达标，应返回-1。
例2：列表[4,3,4,1,2]，initial=3，target=10。初始总和3，依次选1、3、4，累加后为11达标，共需3个元素。

原代码缺陷 #

1. DP初始化错误：用float(-1)表示不可达，会导致min计算逻辑错误，应该用无穷大表示初始不可达状态
2. 未处理动态选择条件：原代码是常规01背包写法，没有考虑“每次选取的元素必须小于当前总和”的核心规则
3. 忽略初始值：默认从0开始累加，不符合需求中从initial开始的设定
4. 未覆盖超过目标值的情况：仅计算刚好等于target的情况，没有处理总和超过target的场景

修正后的代码 #

使用BFS（广度优先搜索）更适合这个问题，因为BFS可以按选元素的数量逐层遍历，第一个满足条件的结果就是最少元素数：

def find_least_numbers_to_exceed_target(numbers, initial, target):
    from collections import deque

    n = len(numbers)
    # 状态：(当前总和, 已使用元素的掩码, 已选元素数量)
    visited = set()
    current_sum = initial
    
    # 初始总和已经达标，直接返回0
    if current_sum >= target:
        return 0
    
    q = deque()
    q.append((current_sum, 0, 0))
    visited.add((current_sum, 0))

    while q:
        current_sum, mask, count = q.popleft()
        for i in range(n):
            # 检查元素是否未被使用
            if not (mask & (1 << i)):
                num = numbers[i]
                # 满足元素小于当前总和的条件
                if num < current_sum:
                    new_sum = current_sum + num
                    new_mask = mask | (1 << i)
                    new_count = count + 1
                    
                    # 达到或超过目标值，返回当前元素数量
                    if new_sum >= target:
                        return new_count
                    
                    # 避免重复处理相同状态
                    if (new_sum, new_mask) not in visited:
                        visited.add((new_sum, new_mask))
                        q.append((new_sum, new_mask, new_count))
    # 所有可能路径都尝试后仍无法达标
    return -1

# 测试示例1
numbers1 = [70, 86, 19]
initial1 = 20
target1 = 80
print(f"例1结果：{find_least_numbers_to_exceed_target(numbers1, initial1, target1)}")  # 输出-1

# 测试示例2
numbers2 = [4, 3, 4, 1, 2]
initial2 = 3
target2 = 10
print(f"例2结果：{find_least_numbers_to_exceed_target(numbers2, initial2, target2)}")  # 输出3

代码说明 #

• BFS遍历逻辑：每一层对应选取k个元素的所有可能状态，因此第一个找到总和≥target的结果就是最少元素数
• 掩码去重：用二进制掩码记录已使用的元素，确保每个元素仅被使用一次
• 状态去重：记录已处理过的(当前总和, 掩码)组合，避免重复计算相同状态
• 动态条件检查：每次选取元素时，严格判断元素是否小于当前总和，符合需求规则

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