Сумма подмножества чисел

Question

Скажем, у меня есть одно число 'n' и таблица чисел. Я хочу выбрать до четырех чисел в таблице, и сумма этих четырех будет максимально приближенным к 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