如何用Solver/Python/R从4万条数据中找精确或近似和为10万的数组合？

你遇到的是子集和问题，针对4万条数据的规模，精确求解（找到完全等于100000的子集）几乎不现实（子集数量达2^40000，远超现有计算能力），但可以通过工具找到近似最优解（最接近目标和的组合），以下是具体实现方案：

1. Excel Solver #

• 局限性：Solver默认的规划求解无法处理4万条数据（需要4万个二进制变量，内存和计算时间完全撑不住）。
• 可行方案：先做数据预处理，筛选出≤100000的数值，再通过启发式策略（比如优先保留接近目标的大数）将数据量压缩到几百条以内，再用Solver求解：
  1. 给筛选后的每条数据分配一个二进制单元格（1表示选中，0表示不选）；
  2. 设置目标函数为「选中数值的和」，约束条件为「和≤100000」，选择「最大化目标函数」；
  3. 运行Solver得到近似最优解。

2. Python 实现 #

Python适合处理大规模数据，优先选择近似算法或启发式算法：

贪心算法（快速高效） #

适合对精度要求不高、追求速度的场景，几秒内可处理4万条数据：

def greedy_subset_sum(numbers, target):
    # 从大到小排序，优先选大数
    sorted_nums = sorted(numbers, reverse=True)
    current_sum = 0
    selected = []
    for num in sorted_nums:
        if current_sum + num <= target:
            current_sum += num
            selected.append(num)
            if current_sum == target:
                break
    return selected, current_sum

# 示例调用
numbers = [你的40000条数据列表]
target = 100000
selected_nums, total = greedy_subset_sum(numbers, target)
print(f"选中数之和：{total}，选中数数量：{len(selected_nums)}")

• 缺点：不一定能找到全局最优解，但足够满足多数场景需求。

遗传算法（近似最优） #

适合需要更优解的场景，通过deap库实现，计算时间可控（几十秒到几分钟）：

from deap import base, creator, tools, algorithms
import random

def genetic_subset_sum(numbers, target, pop_size=100, generations=50):
    # 定义适应度函数：最大化和，惩罚超过目标的情况
    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
    creator.create("Individual", list, fitness=creator.FitnessMax)

    toolbox = base.Toolbox()
    toolbox.register("attr_bool", random.randint, 0, 1)
    toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, n=len(numbers))
    toolbox.register("population", tools.initRepeat, list, toolbox.individual)

    def evaluate(individual):
        total = sum(num * ind for num, ind in zip(numbers, individual))
        return (total,) if total <= target else (target - total,)

    toolbox.register("evaluate", evaluate)
    toolbox.register("mate", tools.cxTwoPoint)
    toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
    toolbox.register("select", tools.selTournament, tournsize=3)

    pop = toolbox.population(n=pop_size)
    algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=generations, verbose=False)

    best_ind = tools.selBest(pop, 1)[0]
    best_sum = sum(num * ind for num, ind in zip(numbers, best_ind))
    selected = [num for num, ind in zip(numbers, best_ind) if ind == 1]
    return selected, best_sum

# 示例调用
selected_nums, total = genetic_subset_sum(numbers, target)
print(f"最优近似和：{total}")

3. R 实现 #

R可通过类似思路实现，以下是常用方案：

贪心算法 #

greedy_subset_sum <- function(numbers, target) {
  sorted_nums <- sort(numbers, decreasing = TRUE)
  current_sum <- 0
  selected <- c()
  for (num in sorted_nums) {
    if (current_sum + num <= target) {
      current_sum <- current_sum + num
      selected <- c(selected, num)
      if (current_sum == target) break
    }
  }
  list(selected = selected, total = current_sum)
}

# 调用示例
numbers <- c(你的40000条数据)
target <- 100000
result <- greedy_subset_sum(numbers, target)
cat("选中数之和：", result$total, "\n")

遗传算法（用GA包） #

library(GA)

genetic_subset_sum <- function(numbers, target) {
  fitness <- function(x) {
    total <- sum(numbers * x)
    if (total > target) return(target - total)
    return(total)
  }

  ga_result <- ga(type = "binary", fitness = fitness, nBits = length(numbers),
                  popSize = 100, maxiter = 50, run = 10)
  
  best_x <- ga_result@solution[1,]
  best_sum <- sum(numbers * best_x)
  selected <- numbers[best_x == 1]
  list(selected = selected, total = best_sum)
}

# 调用示例
result <- genetic_subset_sum(numbers, target)
cat("最优近似和：", result$total, "\n")

关键注意事项 #

1. 预处理优先：先剔除所有大于100000的数值（单个就超目标，无选中意义），再去重冗余小数值，能大幅提升算法效率；
2. 精确解不可行：4万条数据的子集组合量远超计算极限，不要强求完全等于100000的解，优先考虑近似最优解；
3. 工具选择：追求速度用贪心算法，追求精度用遗传算法等启发式方法。

内容的提问来源于stack exchange，提问作者Eduardo Rodrigo Silva Orozco