Алгоритм выбора набора чисел для достижения минимального общего

 pseudocode: list<set> results; int m; list<int> a; // ... a.sort(); for each i in [0..a.size] f(i, empty_set); // ... void f(int ind, set current_set) { current_set.add(a[ind]); if (current_set.sum > m) { results.add(current_set); } else { for (int i=ind + 1; i<a.size; ++i) { f(i, current_set); // pass set by value // if previous call reached solution, no need to continue if (a[ind] + current_set.sum) > m break; } } } // choose whatever "best" result you need from results, the one // with the lowest sum or lowest number of elements 

Это выглядит как классическая проблема динамического программирования (также указываемая другими ответами, в которой упоминается ее сходство с задачами 0-1 Knapsack и Subset Sum). Все это сводится к одному простому выбору: для каждого элемента в списке мы используем его в нашей сумме или нет. Мы можем написать простую рекурсивную функцию для вычисления ответа:

 f(index,target_sum)= 0 if target_sum<=0 (ie we don't need to add anymore) infinity if target_sum>0 and index is past the length of n (ie we have run out of numbers to add) min( f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index] ) otherwise (ie we explore two choices - 1. take the current number 2. skip over the current number and take their minimum) 

Поскольку эта функция имеет перекрывающиеся подзадачи (она снова и снова исследует одни и те же подзадачи), неплохо было бы memoize функцию с кешем для хранения значений, которые уже были вычислены ранее.

Вот код в Python:

 #! /usr/bin/env python INF=10**9 # a large enough number of your choice def min_sum(numbers,index,M, cache): if M<=0: # we have reached or gone past our target, no need to add any more return 0 elif len(numbers)==index: # we have run out of numbers, solution not possible return INF elif (index,M) in cache: # have been here before, just return the value we found earlier return cache[(index,M)] else: answer=min( min_sum(numbers,index+1,M,cache), # skip over this value min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value ) cache[(index,M)]=answer # store the answer so we can reuse it if needed return answer if __name__=='__main__': data=[10,6,3,100] M=11 print min_sum(data,0,M,{}) 

Это решение возвращает только минимальную сумму, а не фактические элементы, используемые для ее создания. Вы можете легко расширить идею, чтобы добавить это к вашему решению.

Я думаю, что будет работать алгоритм жадного алгоритма . Сколько чисел вы ожидаете иметь в комплекте? Если он достаточно низкий, вы можете попробовать вернуться , но я бы не рекомендовал его для больших наборов.

Такие проблемы называются бинарным линейным программированием (частный случай целочисленного линейного программирования). Это классно NP-жесткий – то есть неэффективен для решения в целом.

Тем не менее, существуют хорошие решатели, как коммерческие, так и бесплатные, например, с помощью Open Source solver lpsolve, которые вы можете вызывать из своей программы.

/ EDIT: Старый ответ был нарком. Я смутил факторы.

Я думаю, что это NP-complete ( в общем случае невозможно найти быстрый способ сделать это). То, как вы сформулировали этот вопрос, заставляет задуматься о решении последовательных суммарных задач подмножества с целым целевым числом, которое неуклонно возрастает от M.

В вашем примере нет известного метода определения того, может ли M быть достигнуто. Только решение грубой силы скажет вам, что это невозможно, и только тогда вы можете проверить M + 1.

Тем не менее, вам может понравиться рассмотреть решение DP, поскольку это, по крайней мере, даст вам представление о том, как решить проблему (хотя и медленно). Существует также приблизительное решение, которое будет правильным, если ваши номера малы. Использовать это. Наконец, стоит отметить, что размер проблемы измеряется количеством битов, а не размером (или суммой) набора.

Как упоминалось выше, это связано с проблемой Рюкпак .

Эта проблема представляет собой почти точно проблему суммы подмножества , которая связана с проблемой Кнэпсака, но другая, и является NP полной. Тем не менее, существует линейное решение, если все числа меньше некоторой константы и приближено к полиномиальному времени. См. Страницу с википедии, указанную выше.

Жадное решение работает, если вопрос задает минимальное количество элементов. Но функция максимума (..) должна учитывать, что когда M отрицательный максимум должен вернуть расстояние до 0. (abs () значения).

Функция maximum () может быть реализована через двоичную кучу. Сложность O (n.logn).

Жадное решение будет работать. Псевдо:

 algo(input_set , target_sum, output_set ) if input_set is NULL error "target_sum can never be reached with all input_set" return the_max = maximum(input_set) remove the_max from input_set if the_max > target_sum algo(input_set, target_sum, ouptput_set ) return add the_max to output_set algo(input_set, target_sum - the_max, output_set ) 

вызовите с output_set = NULL. Сортируйте intput_set для эффективности.