求从起始值仅减允许数值以最少步数归零的算法

问题场景 #

给定初始数值 position = 1850，以及允许的减数数组 components = [150, 200, 500]，要求通过仅减去数组中的数值，用最少的操作次数将初始数值减到0。示例中的最优操作是：3次减500、1次减200、1次减150，共5次操作。

核心解法思路 #

1. 贪心算法（高效优先，适用于多数场景） #

贪心的核心逻辑是优先使用最大的减数，每次尽可能多减最大的数，从而减少操作次数。这种方法效率极高，时间复杂度为 O(n log position)（n为数组长度），适合处理大数值的position。

步骤：

• 将components按降序排序，优先处理大数值
• 对当前剩余数值，计算能减去当前最大减数的次数，累加操作次数，更新剩余数值
• 依次处理下一个较小的减数，直到剩余数值为0

伪代码实现：

def min_subtractions_greedy(position, components):
    # 降序排序减数数组
    sorted_components = sorted(components, reverse=True)
    total_steps = 0
    remaining = position
    
    for c in sorted_components:
        if remaining <= 0:
            break
        # 计算当前减数能使用的次数
        use_count = remaining // c
        total_steps += use_count
        remaining -= use_count * c
    
    # 返回次数，若无法归零返回-1
    return total_steps if remaining == 0 else -1

局限性：

贪心算法仅适用于满足贪心选择性质的场景（比如常见的硬币面额系统）。如果components的数值组合不满足该性质，贪心会得到次优解。例如：

• 当 components = [10,7,1]，position =14 时，贪心会选择10+14（5次），但最优解是72（2次）。

2. 动态规划（通用解法，适用于所有场景） #

动态规划通过记录每个数值归零的最少操作次数，逐步推导到目标数值，是通用的最优解方法，时间复杂度为 O(position * n)。

思路：

• 定义 dp[i]：将数值i减到0所需的最少操作次数
• 初始化：dp[0] =0（无需操作），其余dp[i]设为无穷大（表示暂未找到可行解）
• 状态转移：对每个数值i，遍历所有减数c，若i >=c，则 dp[i] = min(dp[i], dp[i-c]+1)

伪代码实现：

def min_subtractions_dp(position, components):
    # 初始化dp数组，无穷大表示无法到达
    dp = [float('inf')] * (position + 1)
    dp[0] = 0
    
    for i in range(1, position +1):
        for c in components:
            if i >= c:
                # 更新当前数值的最少操作次数
                if dp[i - c] +1 < dp[i]:
                    dp[i] = dp[i -c] +1
    
    return dp[position] if dp[position] != float('inf') else -1

3. BFS广度优先搜索（最短路径思路） #

BFS将每个剩余数值视为图中的节点，每次减法操作视为节点间的边，寻找从position到0的最短路径，路径长度即为最少操作次数。这种方法在找到最优解时可立即返回，无需计算所有状态，适合position中等大小的场景。

伪代码实现：

from collections import deque

def min_subtractions_bfs(position, components):
    if position ==0:
        return 0
    
    visited = set()
    # 队列存储(当前剩余数值, 已操作次数)
    q = deque([(position, 0)])
    visited.add(position)
    
    while q:
        current_val, steps = q.popleft()
        for c in components:
            next_val = current_val - c
            if next_val ==0:
                return steps +1
            # 仅处理正数值且未访问过的节点
            if next_val >0 and next_val not in visited:
                visited.add(next_val)
                q.append((next_val, steps +1))
    
    # 无法归零返回-1
    return -1

方法选择建议 #

• 若确定components满足贪心选择性质（比如面额类数值），优先用贪心算法，效率最高
• 若不确定或已知贪心不适用，用动态规划或BFS：
  • 当position较大时，动态规划可能占用较多内存，BFS更灵活
  • 当position较小时，两种方法差异不大

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