从数值数组中按百分比选取最优候选子集的算法问询

这问题其实是经典的背包问题变种——咱们要在「总和不超过阈值」的约束下，优先选大元素，甚至尽可能让子集总和接近阈值。你之前算法不稳定，大概率是没抓住这类问题的核心思路，我给你梳理几个可行的方案，从简单到精准：

这是最直观的思路，优先拿大元素，能满足大部分场景的需求，而且实现简单、速度快：

• 步骤：

  1. 把数组按降序排序
  2. 依次遍历排序后的元素，只要加上当前元素后总和不超过阈值，就把它加入子集
  3. （可选优化）选完大元素后，如果阈值还有剩余空间，从剩下的小元素里挑能塞进去的，尽量填满阈值（比如从剩下的元素里找最大的能塞进去的）

• Python示例代码：

def greedy_subset(arr, threshold):
    sorted_arr = sorted(arr, reverse=True)
    subset = []
    current_sum = 0
    for num in sorted_arr:
        if current_sum + num <= threshold:
            subset.append(num)
            current_sum += num
    # 可选优化：用剩余空间补小元素
    remaining = threshold - current_sum
    if remaining > 0:
        # 从剩下的元素里找最大的能塞进去的
        remaining_nums = [num for num in arr if num not in subset]
        remaining_nums.sort(reverse=True)
        for num in remaining_nums:
            if num <= remaining:
                subset.append(num)
                current_sum += num
                remaining -= num
                if remaining == 0:
                    break
    return subset, current_sum

• 注意：贪心不是总能得到最优解（比如数组[1000,900,900]，阈值1800时，贪心会选1000，但最优解是两个900），但如果你的数组里大元素之间没有这种“互补”的情况，贪心足够用。

如果需要绝对精准的最优解（子集总和尽可能接近阈值，同时优先包含大元素），动态规划是靠谱的选择，适合元素数量不多的场景：

• 思路：

  1. 定义dp[j]表示是否存在总和为j的子集
  2. 初始化dp[0] = True（空子集总和为0）
  3. 先把数组降序排序（优先处理大元素，后续回溯时能更快拿到大元素组成的子集）
  4. 遍历每个元素，从阈值倒着遍历到元素值，更新dp[j] = dp[j] or dp[j - num]
  5. 找到最大的j <= 阈值使得dp[j] = True，然后回溯找到对应的子集

• Python示例代码：

def dp_optimal_subset(arr, threshold):
    sorted_arr = sorted(arr, reverse=True)
    dp = [False] * (threshold + 1)
    dp[0] = True
    # 记录每个总和对应的最后一个加入的元素，方便回溯
    prev = [-1] * (threshold + 1)
    
    for num in sorted_arr:
        for j in range(threshold, num - 1, -1):
            if dp[j - num] and not dp[j]:
                dp[j] = True
                prev[j] = num
    
    # 找最大的可行总和
    max_sum = 0
    for j in range(threshold, -1, -1):
        if dp[j]:
            max_sum = j
            break
    
    # 回溯找子集
    subset = []
    current = max_sum
    temp_arr = sorted_arr.copy()
    while current > 0:
        num = prev[current]
        subset.append(num)
        current -= num
        # 避免重复选同一个元素（如果数组有重复的话）
        if num in temp_arr:
            temp_arr.remove(num)
    return subset, max_sum

如果数组元素数量很多，动态规划的空间开销会很大（阈值大的话dp数组会非常大），这时候分支限界法更合适，通过剪枝减少不必要的计算：

• 思路：

  1. 先把数组降序排序，计算后缀和（方便快速知道剩余元素的总和）
  2. 递归尝试两种选择：选当前元素（如果总和不超），或者不选
  3. 剪枝条件：
     • 如果当前总和 + 剩余所有元素的总和 <= 当前找到的最优解，直接放弃这条分支
     • 如果当前总和 + 当前元素 > 阈值，直接跳过选当前元素的分支
  4. 记录过程中找到的最大总和对应的子集

• 核心思想是优先探索选大元素的分支，一旦找到更优解就更新，然后剪枝掉不可能更优的分支，效率比暴力搜索高很多。

总结一下：

• 如果追求速度，且对“最优”要求不高，用贪心算法
• 如果数组规模小（比如元素数<100），阈值也不大，用动态规划拿精准解
• 如果数组规模大或者阈值很大，用分支限界法

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