Он также начинается с сортировки чисел в порядке убывания.
Вот результат сортировки списка [8,7,6,5,4]
На каждом шаге алгоритм берет на себя обязательство поместить два самых больших числа в разные подмножества, откладывая решение о том, какое подмножество будет входить в каждое.
В приведенном выше примере, если мы поместим 8 в левом подмножестве и 7 в правом подмножестве, это эквивалентно размещению их разницы 1 в левом подмножестве, так как мы можем вычесть 7
из обоих подмножеств, не влияя на окончательную разницу. Аналогично размещение 8
в правом подмножестве и 7 в левом подмножестве эквивалентно размещению 1 в
правое подмножество.
Алгоритм удаляет два самых больших числа, вычисляет их
разница, а затем обрабатывает разницу, как и любое другое число, чтобы быть
назначается, вставляя его в отсортированном порядке в оставшийся список номеров.
Алгоритм продолжает удалять два самых больших числа, заменяя их на
их различие в отсортированном списке, пока не останется только один номер, который
является значением окончательной разности подмножеств.
Например, , учитывая отсортированные целые числа (8,7,6,5,4), 8 и 7 заменяются их разностью 1, которая вставляется в оставшийся список, в результате чего
в (6,5,4,1). Далее 6 и 5 заменяются их разностью 1, что приводит к
(4,1,1). 4 и 1 заменяются их разностью 3, давая (3,1), и
наконец, разница этих двух последних чисел является окончательной разницей в подмножестве
из 2.
Эвристика KK также не может найти оптимальное разбиение в этом случае, но работает лучше, чем жадная эвристика.
Проблема с разделением номера Скачать PDF