高效求解数组元素组合的最小与最大达标和（满足不跳过约束的贪心+堆优化算法）-Python教程-PHP中文网

高效求解数组元素组合的最小与最大达标和（满足不跳过约束的贪心+堆优化算法）

本文介绍一种基于优先队列（最小堆）的高效算法，用于在给定有序整数数组和目标阈值 limit 下，找出所有合法累加序列中 ≥limit 的最小和与最大和；关键约束是：累加必须从数组起始位置开始、不可跳过中间元素、允许重复使用当前及后续元素。

本文介绍一种基于优先队列（最小堆）的高效算法，用于在给定有序整数数组和目标阈值 limit 下，找出所有合法累加序列中 ≥limit 的最小和与最大和；关键约束是：累加必须从数组起始位置开始、不可跳过中间元素、允许重复使用当前及后续元素。

该问题本质是一个带约束的有向图路径搜索问题：数组索引构成节点，每一步可选择“停留在当前索引继续累加”或“前进到下一索引再累加”，目标是在首次达到或超过 limit 时，记录所有可行路径对应的和，并从中提取全局最小值与最大值。

核心约束解析

✅ 不可跳过元素：意味着累加序列必须由连续前缀（从 arr[0] 开始）的若干次扩展构成，即若当前在索引 i，下一步只能用 arr[i]（重复）或切换至 arr[i+1]（前进），但不能直接跳到 arr[i+2]。
✅ 允许重复使用：在索引 i 处可多次添加 arr[i]，直到决定前进。
✅ 首次达标即终止：一旦当前和 ≥ limit，该路径即为一个候选解，无需继续扩展。

上述约束排除了完全背包或子集和等经典模型——它不是任意组合，而是具有顺序依赖性的路径生成过程。

算法设计：Dijkstra 变体 + 双目标追踪

暴力递归易栈溢出且重复计算严重；动态规划难以定义状态维度（因路径长度无界）。最优解是采用最小堆驱动的状态空间搜索：

Raphael AI

一款AI图像生成工具，可根据文字描述生成图片，适合进行创意视觉探索、插画制作和多种图像创作任务。

下载

每个状态为 (current_sum, current_index, path)，按 current_sum 小顶堆排序，优先探索更小和；
使用 known 字典去重：键为 (sum, index)，避免相同和+位置的冗余路径；
遍历时对每个状态生成两个分支：
1. 停留复用：sum += arr[i]，索引 i 不变；
2. 前进切换：sum 不变，索引 i → i+1（仅当 i+1
一旦 sum ≥ limit，立即更新 best_min 和 best_max，并终止该路径扩展。

⚠️ 注意：原题示例中 [100, 200, 300, 1000, 10000] 在递归方法中返回 10900 是错误的——因为 10000 单独已 ≥1000，但按约束必须从 arr[0]=100 开始累加，故 10000 无法被单独选取（除非先经过 100→200→300→1000→10000 序列，其和远超 10900）。正确最小和仍是 1000（10×100），最大和为 1900（100+200+300+300+1000），验证了算法对约束的严格遵守。

Python 实现（健壮版）

import heapq
from typing import Tuple, Optional, List

def min_max_limit_sum(arr: List[int], limit: int) -> Tuple[int, int]:
    if not arr or limit = limit, update results and skip expansion
        if s >= limit:
            best_min = min(best_min, s)
            best_max = max(best_max, s)
            continue

        # Cannot proceed beyond array bounds
        if i >= len(arr):
            continue

        # Branch 1: Use arr[i] again (stay at same index)
        new_s1 = s + arr[i]
        heapq.heappush(heap, (new_s1, i, path + (arr[i],)))

        # Branch 2: Move to next index (advance)
        if i + 1 <h3>关键优势与注意事项</h3>