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

Question

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

Answer 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} 

Generation 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} 

Generation 4:

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

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

Answer 2

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

Answer 3

Split проблема на 4 части:

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

  Просто петли до конца и найти самое высокое значение не больше, чем цель.

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

  Используйте двойной для цикла, чтобы найти самую большую сумму не больше, чем цель.

• Сумма, содержащая ровно три элемента (по аналогии с 3SUM)

  сортирует элементы

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

• Сумма содержащих ровно 4 элементы

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

  использовать двойной для контура, чтобы генерировать все суммы 2-х элементов.

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

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

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

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