Проблема с пользовательским разделом

Question

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

Например: N = 4 Номера: 20 5 3 1

Результат: 15

Пояснение: Первое число будет разделено на два, и каждая половина будет помещена в один из двух разделов => первый раздел = 10, второй раздел = 10. Второй номер будет добавлен в первый раздел => первый раздел = 15. Последние два номера будут добавлены во второй раздел => второй раздел = 14

=> сумма большего раздела (первого раздела) = 15.

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

Также для следующего набора данных алгоритм даст правильный ответ: N = 2 Номера: 16 15

=> займет 15, добавит его к первому разделу, а затем 16 см. Неоптимально разделить его на два, поэтому он добавит его ко второму разделу.

=> ответ будет 16.

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

Спасибо! :)

Answer 1

Я бы просто разделил все четные числа за один проход, а затем применил классический алгоритм разделения.Или есть какая-то вторичная цель, чтобы минимизировать количество расколов?

Answer 2

проблема разбиения является NP-полной, что означает, что алгоритм полиномиального времени вряд ли существует.Ваш модифицированный вариант также NP-завершен;редукция к оригинальной версии довольно проста.

Answer 3

Почему бы вам не разделить каждое число пополам и добавить 1 для нечетных чисел в циклических разделах?2-й раздел всегда будет иметь меньшую сумму.

List: 20 17 6 5 3 0 -1 9999999</p>

<p>P1: 10 | 8+1 | 3 | 2   | 1+1 | 0 | -1   | 4999999+1 |  ==> sum is 5000025
P2: 10 | 8   | 3 | 2+1 | 1   | 0 | -1+1 | 4999999   |  ==> sum is 5000024