You need to enable JavaScript to run this app. 咨询带优先级数值按降序选数且总价值不超约束的算法名称
优惠活动
大模型
产品
解决方案
定价
更多

咨询带优先级数值按降序选数且总价值不超约束的算法名称

对应算法名称

这个场景匹配的是优先级约束下的顺序贪心选择算法,是贪心算法的一类变体。该算法的核心约束是优先级顺位优先于价值最大化,即决策逻辑完全不考虑总价值是否能达到全局最高,只严格按优先级高低判断是否在不超约束的前提下保留元素。它和经典0/1背包算法的核心差异在于,经典0/1背包追求最终选取元素的总价值尽可能高,允许为了更高价值跳过高优先级元素,而本算法中优先级规则拥有绝对决策权重。

核心实现逻辑

整个流程完全适配任意规模的元素集合,无数量上限,步骤可拆解为:

  • 预过滤环节:遍历所有待选元素,将自身价值已经超过给定约束值的元素直接剔除——这类元素无论优先级高低,单值就已突破上限,不存在被选取的可能。
  • 排序环节:把预过滤后剩余的候选元素,按照优先级数值从高到低做降序排列;同优先级的元素可以根据业务需要补充次级排序规则(比如同优先级下优先选价值更高的元素,或保持元素原始输入顺序做稳定排序)。
  • 顺序累加判断环节:初始化总累计价值为0,从优先级最高的元素开始依次遍历:
    • 若当前累计价值 + 当前元素价值 ≤ 给定约束值,则将该元素纳入最终选取集合,同时把当前元素价值叠加到累计值上
    • 若叠加后超过约束值,则直接跳过该元素,继续判断下一个优先级的元素
    • 遍历完所有候选元素后流程终止
结合示例的流程验证

拿题目给出的案例走一遍完整流程:待选元素为「(优先级3, 价值2)、(优先级1, 价值3)、(优先级2, 价值9)」,约束值为4。

  1. 预过滤:价值9的元素单值9>4,直接排除,剩余候选为(3,2)、(1,3)
  2. 排序:按优先级降序排完后的元素顺序为(3,2)、(1,3)
  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,提问作者Иван Шемет

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.27 19:24:01