说我有一个数字“n”和数字的表格。 我想选择了在表中的数字的4个，这四个的总和将是最接近的可能匹配到n。 给定长度表中的 'L'，它要经过组合的数量是（6 * L + 11 * L ^ 2 + 6 * L ^ 3 + L ^ 4）/ 24。
恩。 说我有变数
n = 100
和组数字
t = {86, 23, 19, 8, 42, 12, 49}
鉴于这一列表中，四个至n最接近的组合是49 + 23 + 19 + 8 = 99。
什么是计算尽可能少的数量这样做的最佳方式？
Answer 1:
这看起来像“子集和”的变化（参见： http://en.wikipedia.org/wiki/Subset_sum_problem ）这是众所周知的是NP完全问题，所以很遗憾很可能不会有任何聪明的算法在所有的，在最坏情况下将运行得更快的是指数中的项目数量。
如果没有很多检查项目（东西约10个左右），你可能会尽快尝试深度优先搜索剪枝。
如果有更多的检查项目的最有可能不是寻找最佳的解决方案，你可以更好地试图找到一个好几分近似。
Answer 2:
假设所有的数字是正整数，这是可以做到的Yexo指出：
local n = 100
local t = {86, 23, 19, 8, 42, 12, 49}
local max_terms = 4
-- best[subset_size][terms][k] = {abs_diff, expr}
local best = {[0] = {}}
for k = 1, n do best[0][k] = {k, ''} end
for terms = 0, max_terms do best[terms] = best[0] end
for subset_size = 1, #t do
local new_best = {}
for terms = subset_size == #t and max_terms or 0, max_terms do
new_best[terms] = {}
for k = subset_size == #t and n or 1, n do
local b0 = best[terms][k]
local diff = k - t[subset_size]
local b1 = terms > 0 and (
diff > 0 and {
best[terms-1][diff][1],
best[terms-1][diff][2]..'+'..t[subset_size]
} or {math.abs(diff), t[subset_size]}
) or b0
new_best[terms][k] = b1[1] < b0[1] and b1 or b0
end
end
best = new_best
end
local expr = best[max_terms][n][2]:match'^%+?(.*)'
print((loadstring or load)('return '..expr)()..' = '..expr)
-- Output
99 = 23+19+8+49
文章来源: Sum of a subset of numbers
