Распределите числа по двум «контейнерам» и минимизируйте разницу их суммы

Question

Предположим, что есть n чисел, пусть говорит, что у нас есть следующие 4 числа 15,20,10,25

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

В приведенном выше примере A должно иметь 15 + 20, а B должно иметь 10+ 25. Таким образом, разница = 0.

Я думаю о методе.Кажется, это работает, но я не знаю почему.

Сортировка списка номеров в порядке убывания.В каждом раунде вынимайте максимальное количество и кладите в контейнер меньшую сумму.

Кстати, это можно решить с помощью DP?THX

Answer 1

1. На самом деле, ваш метод не всегда работает .Подумайте об этом 2,4,4,5,5. Результат по вашему методу будет (5,4,2)(5,4), тогда как лучший ответ будет (5,5)(4,4,2).

2. Да, это может бытьрешено Динамическое программирование . Вот несколько полезных ссылок:

   Учебник и код: http://www.cs.cornell.edu/~wdtseng/icpc/notes/dp3.pdf
   Практика: http://people.csail.mit.edu/bdean/6.046/dp/ (затем нажмитеBalanced Partition)

3. Более того, обратите внимание, что если масштаб проблемы чертовски большой (например, у вас 5 миллионов номеров и т. Д.), Вы не захотитеиспользуйте DP, который нуждается в слишком большой матрице.Если это так, вы хотите использовать своего рода алгоритм Монте-Карло :

   1. случайным образом разделить n чисел на две группы (или использовать ваш метод на этом шагеесли хочешь);
   2. выберите один номер из каждой группы,если (чтобы поменять местами эти два числа уменьшить разницу в сумме) поменять их местами;
   3. повторять шаг 2 до тех пор, пока "обмен долгое время не происходил".

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