如何找到总和刚好高于阈值的元素组合

Question

我有一个问题陈述：如果你有一个元素数组 {x1,x2,x3,...x10}，找到元素的组合，使其总和超过阈值（比如阈值为 100)。

所以如果存在x2+x5+x8 = 105、x3+x5+x8=103、x4+x5 = 101这样的组合，那么算法应该输出X4、X5。

背包算法发出的值接近但在阈值的较小一侧（此处为 100）。我想要相反的，即大于100的所选元素的最小总和。

是否有任何算法集或任何算法的任何特例可以解决这个问题？

Answer 1

首先我会注意到您要求的是严格大于某个目标的最小值。通常 "strictly greater than" 和 "strictly less than" 约束比 "greater than or equal to" 或 "less than or equal to" 约束要难得多。如果你有所有整数值，那么你可以简单地 t运行将你的约束 "the sum exceeds 100" 设置为 "the sum is greater than or equal to 101"。我假设你已经为问题的其余部分做了这样一个 t运行sformation。

一种方法是将其视为整数优化问题，其中每个数字的二元决策变量 y_i 是我们是否包含它。那么我们的目标就是最小化数字的总和，可以建模为：

min x_1*y_1 + x_2*y_2 + ... + x_n*y_n

本例中的约束条件是数字之和至少为 100:

x_1*y_1 + x_2*y_2 + ... + x_n*y_n >= 100

总的来说，这是一个难题（请注意，它至少与 NP 完全的子集求和问题一样难）。然而，现代优化求解器可能对您的问题实例足够有效。

要测试此问题的免费求解器的可扩展性，请考虑使用 R 中的 lpSolve 包进行以下实现（如果问题是 returns selected 子集可行，否则 NA)：

library(lpSolve)
min.subset <- function(x, min.sum) {
  mod <- lp("min", x, matrix(x, nrow=1), ">=", min.sum, all.bin=TRUE)
  if (mod$status == 0) {
    which(mod$solution >= 0.999)
  } else {
    NA
  }
}
min.subset(1:10, 43.5)
# [1] 2 3 4 5 6 7 8 9
min.subset(1:10, 88)
# [1] NA

为了测试可伸缩性，我将从 [1, 2, ..., 1000] 中 select n 个元素运行domly，将目标总和设置为元素总和的一半。运行时间为：

与 n=100 相比，它运行在 0.01 秒内
使用 n=1000，它运行在 0.1 秒内
使用 n=10000，它运行在 8.7 秒内

看来您可以解决超过 10k 个元素的问题（使用 selected 分布），而不会遇到太多计算挑战。如果您的问题对于我在这里使用的免费求解器来说太大了，您可以考虑使用 Gurobi 或 cplex，这两个商业求解器可免费用于学术用途，但在其他方面并非免费。

Answer 2

假设X是所有x_i的总和。然后等效地，您要求 x_i 的最小子集总和最多 X - 100 （因为这些 x_i 的补充将是您问题的最佳解决方案）。所以所有的背包理论都可以应用到这里。

在实践中（非常大的实例），我建议 this 形式的 Nemhauser-Ullman 泛化，它可以解决具有数百万个对象的实例。

如何找到总和刚好高于阈值的元素组合

How to find a combination of elements that sum up just above threshold value

algorithm

optimization

mathematical-optimization

genetic-algorithm

knapsack-problem