Учитывая целевую сумму и набор целых чисел, найдите ближайшее подмножество чисел, добавляющих к этой цели

У меня есть набор целых чисел M и целевой суммы k. Я хочу найти подмножество M, которое при объединении ближе всего к k, не переходя.

Например:

M = {1, 3, 5, 5, 14}

k = 12

answer = {1, 5, 5}

because 1 + 5 + 5 = 11 and there is no way to make 12.

У меня есть дополнительное ограничение, что подмножество может содержать не более 4 элементов.

В моем приложении размер | M | может быть большим (порядка тысяч элементов). Если в течение разумного времени невозможно найти оптимальный ответ, меня интересуют решения, которые, по крайней мере, дают "хороший" ответ.

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

Ответ 1

Поскольку у вас есть ограничение на количество элементов, которые вы можете выбрать, вы можете сделать это с помощью достаточно простого алгоритма.

Алгоритм дает возможные суммы в "поколениях". Каждый элемент поколения состоит из числа, представляющего сумму, и N-кортежей индексов в M, которые использовались для построения этой суммы.

Ноль покоя пуст; поколение X+1 создается путем перехода поколения X и добавления элементов M к каждому значению этого поколения и записи их суммы для следующего поколения X+1.

Перед вычислением суммы проверьте его N-кортеж на наличие индекса числа, которое вы собираетесь добавить. Если он там, пропустите номер. Затем проверьте сумму: если она уже присутствует среди сумм X+1, игнорируйте ее; в противном случае запишите новую сумму вместе с новым N-кортежем индексов (добавьте индекс числа, добавленного в N-кортеж из поколения X).

Вот как это будет работать для ваших входов:

Поколение 0: пусто

Поколение 1:

 1 - {0}
 3 - {1}
 5 - {2}
14 - {4}

Поколение 2:

 4 - {0, 1}
 6 - {0, 2}
 8 - {1, 2}
10 - {2, 3}
15 - {0, 4}
17 - {1, 4}
19 - {2, 4}

Поколение 3:

 9 - {0, 1, 2}
11 - {0, 2, 3}
13 - {1, 2, 3}
18 - {0, 1, 4}
20 - {0, 2, 4}
22 - {1, 2, 4}
24 - {2, 3, 4}

Поколение 4:

14 - {0, 1, 2, 3}
23 - {0, 1, 2, 4}
25 - {0, 2, 3, 4}
27 - {1, 2, 3, 4}

Теперь вы можете выполнить поиск по четырем поколениям для числа, которое ближе всего к вашему целевому номеру k.

Ответ 2

Если целевая сумма k не слишком велика, посмотрите http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution - вы можете использовать это для создания растрового изображения, которое сообщает вам, номера могут быть получены с использованием вашего подмножества. Затем просто выберите максимально возможное число до k в растровом изображении.

Ответ 3

Разделите проблему на 4 части:

Сумма, содержащая ровно 1 элемент

Просто пройдите и найдите максимальное значение, не превышающее цель.
Сумма, содержащая ровно 2 элемента

Используйте двойной цикл for, чтобы найти самую большую сумму, не превышающую цель.
Сумма, содержащая ровно 3 элемента (аналогично 3SUM)

Сортировка элементов

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

Сортировка элементов (уже сделано)

Используйте двойной цикл for для создания всех сумм из двух элементов.

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

См. this для кода, использующего этот подход для аналогичной проблемы (точную сумму).

Среднее время пробега (?) = O(n + n^2 + n^2 log n + n^2 log n) = O(n^2 log n).

Определить время работы последней проблемы несколько сложно, это может быть так же плохо, как O(n^4 log n) в худшем случае, так как вы можете в конечном итоге просмотреть большинство из них, прежде чем найти тот, который подходит, но это редко происходят, и, в рамках одного и того же запуска, некоторые должны занимать меньше времени, поэтому общее время работы может быть меньше.