如何在集合中找到数字组合，使其最大程度接近目标值（与目标值的差距最小）？该问题涉及IT技术。

Question

如何在集合中找到数字组合，使其最大程度接近目标值（与目标值的差距最小）？该问题涉及IT技术。

3

我希望找到一种解决方案，用于查找大型数集中最接近目标数字的子集。例如，我有一个数值集合：

   c(55.14, 26.22, 76.69, 37.77, 32.7, 48.71, 7.59, 21.37, 33.54, 3.95, 16.41, 
20.56, 24.74, 26.5, 4.72, 32.99, 130.15, 27.27, 20.56, 41.21, 13, 16.41, 88.25, 
1.95, 68.2, 34.3, 51.75, 8.93, 8.38, 30.45, 34.89, 42.91, 19.42, 13.62, 9.73, 
20.86, 21.5, 37.46, 14.4, 26.61, 55.31, 24.03)

我的目标是1262.2。

我该如何找到完整集合中使得子集总和与目标值1262.2之间差异最小的子集？

- tlev

如果您知道要从集合x中选择多少个数字，请使用combn(x，n) - 这将给出所有包含n个数字的x可能集合，然后对它们求和并找到最小值。重复任何n以找到最小值（准备等待！）。 - Remko Duursma

@Remko - 根据一些快速计算 - sum(sapply(1:length(x), function(y) choose(length(x),y) )) 其中 x 是上面的向量，将有 4398046511103 种可能的组合需要检查。那是四万亿多一点。正如您所指出的，OP可能应该有一些限制来使这个过程可管理。 - thelatemail

1

你需要很多组合还是只需要一个就可以？一个快速的解决方法是对集合中的所有元素进行排序，并运行一个for循环，将集合中的所有元素相加，直到它小于你的目标为止。这是一个快速的解决方法，比检查所有组合返回结果的时间更短。 - Dinesh.hmn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- G. Grothendieck · Accepted Answer

假设v是问题中显示的值向量。

假设x是一个未知的、长度相同、包含0-1变量的向量。

然后在x上运行这两个整数线性规划，选择目标最接近1262.2的解作为答案。（这里 * 表示内积。）

max(v*x) such that v*x <= 1262.2

min(v*x) such that v*x >= 1262.2

使用Rglpk我们得到了以下结果，由于我们已经达到了精确的1262.2，因此我们不需要再去处理第二个整数线性规划问题：

library(Rglpk)

ans <- Rglpk_solve_LP(v, t(v), "<=", 1262.2, max = TRUE, types = "B")

提供：

> ans[1:3]
$optimum
[1] 1262.2

$solution
 [1] 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1

$status
[1] 0

注意第一个整数线性规划问题被称为背包问题，我们可以使用adagio中的knapsack来解决它。

library(adadgio)

v100 <- as.integer(100 * v)
knapsack(v100, v100, 126220L)

（尽管在其帮助页面上没有提到，但背包问题需要整数参数。）