如何找到总结刚刚超过阈值的元素组合

我有一个问题陈述，说：如果你有一个元素{x1，x2，x3，... x10}的数组，找到元素的组合使得它仅仅总计超过阈值（比如阈值为100）。如何找到总结刚刚超过阈值的元素组合

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

背包算法发出的值接近但低于阈值（这里为100）。我想要的是相反的，即大于100的所选元素的最小总和。

是否有任何一组算法或任何可能解决此问题的算法的特例？

2015-10-06 Argho Chatterjee

你可以尝试改变硬币改变算法。优化的Coin变化可用于查找O（n）空间中数字数组的所有子集的个别和。但跟踪哪个子集形成的特定总和是棘手的。看看这个算法的简化版本[这里]（http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/） –

我会首先注意到你要求的最小值严格大于某个目标。一般来说，“严格大于”和“严格小于”约束比“大于或等于”或“小于或等于”约束要困难得多。如果你有所有的整数值，那么你可以简单地把你的约束“总和超过100”翻译成“总和大于或等于101”。我会假设你已经为剩下的问题做了这样的转换。

一种方法是将其视为整数优化问题，其中每个数字的二元决策变量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完全问题）。然而现代优化求解器对于你的问题实例可能是有效的。

要测试的自由解算器的可扩展性对于这个问题，考虑与lpSolve包R（它返回所选择的子集，如果问题是可行的，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]中随机选择n元素，将目标和设置为元素总和的一半。运行时间为：

随着n=100，它在0.01秒内
跑了n=1000，它在0.1秒内
跑了n=10000，它8.7秒跑

看样子你可以针对超过10k个元素（使用选定的分布）解决此问题，而不会有太多的计算难题。如果你的问题对于我在这里使用的免费解算器来说太大了，你可能会考虑Gurobi或者cplex这两个商业解算器，它们可以免费用于学术用途，但是不是免费的。

来源

2015-10-06 17:24:30 josliber

嘿@Josiber，我试图在java中实现它，如果你可以提供任何sudo代码或视频教程链接，对你的实施真的会有所帮助，再次感谢你的努力。 –

@ArghChatterjee我会鼓励你自己尝试实现它，并发布一个新的问题是你碰到任何实现问题。 – josliber

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

在实践中（真的很大的情况下），我建议this形式的Nemhauser-Ullman泛化，它可以解决数百万个对象的实例。

来源

2015-10-06 17:44:15 m8mble

如何找到总结刚刚超过阈值的元素组合

回答

相关问题