数集的子集和

2013-3-26 19:34:13
收藏：0
阅读：144
评论：2

假设我有一个数 n 和一个数字表。我想从表格中选择最多四个数字，这四个数字的和将最接近 n。给定表的长度 L，要穷举的组合数为(6L + 11L^2 + 6*L^3 + L^4)/24。

例如，假设变量为

n = 100

数字集合为

t = {86, 23, 19, 8, 42, 12, 49}

给定此列表，最接近 n 的四个数字的组合为 49 + 23 + 19 + 8 = 99。

使用最少的计算量，最佳方法是什么？

点赞
用户2056411
用户2056411

这似乎是“子集和问题”的一个变体（参见：http://en.wikipedia.org/wiki/Subset_sum_problem），已知这是 NP 完全问题，所以不幸的是，最坏情况下运行速度可能不会比指数级算法更快。

如果要检查的项不多（约为 10 个左右），则可以尝试深度优先搜索，并尽早修剪分支。

如果要检查的项很多，最好尝试找到一个近似的解，而不是搜索最优解。

2013-03-26 19:37:15
用户1847592
用户1847592

假设所有数字都是正整数，可以像 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)

-- 输出
99 = 23+19+8+49
2013-03-26 20:46:38

作者:

用户1510913

用户1510913
推荐文章