咨询带优先级数值按降序选数且总价值不超约束的算法名称
对应算法名称
这个场景匹配的是优先级约束下的顺序贪心选择算法,是贪心算法的一类变体。该算法的核心约束是优先级顺位优先于价值最大化,即决策逻辑完全不考虑总价值是否能达到全局最高,只严格按优先级高低判断是否在不超约束的前提下保留元素。它和经典0/1背包算法的核心差异在于,经典0/1背包追求最终选取元素的总价值尽可能高,允许为了更高价值跳过高优先级元素,而本算法中优先级规则拥有绝对决策权重。
核心实现逻辑
整个流程完全适配任意规模的元素集合,无数量上限,步骤可拆解为:
- 预过滤环节:遍历所有待选元素,将自身价值已经超过给定约束值的元素直接剔除——这类元素无论优先级高低,单值就已突破上限,不存在被选取的可能。
- 排序环节:把预过滤后剩余的候选元素,按照优先级数值从高到低做降序排列;同优先级的元素可以根据业务需要补充次级排序规则(比如同优先级下优先选价值更高的元素,或保持元素原始输入顺序做稳定排序)。
- 顺序累加判断环节:初始化总累计价值为0,从优先级最高的元素开始依次遍历:
- 若当前累计价值 + 当前元素价值 ≤ 给定约束值,则将该元素纳入最终选取集合,同时把当前元素价值叠加到累计值上
- 若叠加后超过约束值,则直接跳过该元素,继续判断下一个优先级的元素
- 遍历完所有候选元素后流程终止
结合示例的流程验证
拿题目给出的案例走一遍完整流程:待选元素为「(优先级3, 价值2)、(优先级1, 价值3)、(优先级2, 价值9)」,约束值为4。
- 预过滤:价值9的元素单值9>4,直接排除,剩余候选为(3,2)、(1,3)
- 排序:按优先级降序排完后的元素顺序为(3,2)、(1,3)
- 累加判断:初始累计值为0
- 先判断优先级最高的价值2:0+2=2≤4,纳入集合,累计值更新为2
- 再判断下一个价值3:2+3=5>4,直接跳过
最终选取结果为仅选价值2,和案例给出的结果完全一致。
通用实现伪代码
def priority_constraint_select(item_list, max_total_limit): # item_list 单元素结构为 (priority, item_value) # 第一步:过滤单值超限制的元素 valid_items = [item for item in item_list if item[1] <= max_total_limit] # 第二步:按优先级从高到低排序 valid_items.sort(key=lambda x: -x[0]) selected_items = [] current_total = 0 # 第三步:顺序遍历判断 for item_priority, item_value in valid_items: if current_total + item_value <= max_total_limit: selected_items.append(item_value) current_total += item_value return selected_items, current_total
内容的提问来源于stack exchange,提问作者Иван Шемет
相关产品推荐
相关产品推荐

