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

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-й раздел всегда будет иметь меньшую сумму.

Список: 20 17 6 ​​5 3 0 -1 9999999
P1: 10 | 8 + 1 | 3 | 2 | 1 + 1 | 0 | -1 | 4999999 + 1 | ==> сумма 5000025
P2: 10 | 8   | 3 | 2+1 | 1   | 0 | -1+1 | 4999999   |  ==> сумма 5000024