Как расставить шесть чисел так, чтобы сумма первых трех была примерно равна сумме остальных?

Question

[Константин Китманов]

Стоит задача красиво нарисовать кольцевую диаграмму. Диаграмма всегда состоит из шести секторов; справа и слева — по тре легенды с указателями. Соответственно, чтобы это все было более-менее симметрично, надо скормить библиотеке, отвечающей за рендер диаграммы, данные в правильном порядке. То есть, чтобы (a₀ + a₁ + a₂) - (a₃ + a₄ + a₅) было минимальным из всех возможных.

Можно было бы просто перебрать все возможные перестановки массива из шести элементов, но это, ЕМНИП, 6! == 720 перестановок, а дело происходит в браузере, в JS, и в таком месте, где тормоза никак не допустимы.

Сумма чисел будет равна, очевидно, 100 (ибо 100%).

Answer 1

[vans239]

Что-то вы преувеличили количество необходимых перестановок. Выбор левой тройки однозначно определяет выбор правой тройки (а также ее сумму). Поэтому всего необходимо перебрать 6!/(3!*3!) = 20. А это уже мало

Comments

[Константин Китманов]

Да, вы правы.

Answer 2

[Артем Калачян]

Частное от задачи о двух кучах камней - распространенной на олимпиадах как представитель динамического программирования. Неплохо расписано здесь, но вряд ли шкурка стоит вычинки. Проще раскидать приблизительно - кидаем самый большой кусок на одну кучу. Если меньше 50%, докидываем самых маленьких. На этапе, когда станет больше 50% возвращаемся на шаг назад. Либо не возврашаемся, если не намного больше. Остальное уходит во вторую "кучу"

Comments

[Константин Китманов]

Посмотрю, что будет давать лучшие результаты. За ссылку на алгоритм огромное спасибо!

Answer 3

[Владлен Грачев]

Отсортировать и взять в первую выборку четные элементы, а во вторую - нечетные. Не факт, что это даст лучший результат, но просто, быстро и первое, что приходит на ум.

Результат будет ближе к нужному, если в каждый набор брать по очереди сначала четный элемент, потом нечетный. Допустим, есть отсортированный набор: 1,2,3,4,5,6.

Берем: (1, 4, 5), (2,3,6). Это уже лучше, чем (1, 3, 5), (2, 4, 6). Так как мы не берем каждый раз в набор с четными элементами заведомо больший элемент, а чередуем.

Если числа в сумме дают что-то определенное (100 или 1, например), то можно попробовать реализовать направленный поиск набора, наиболее близкого к половине от суммы.

Comments

[Константин Китманов]

@gwer, как вариант, да… можно в первую выборку 0, 2 и 5 элементы брать, а во вторую 1,3 и 4 — будет «поровнее», мне кажется.

[Владлен Грачев]

@k12th, да, сразу после отправки вспомнил про это, пока редактировал комментарий, вы уже ответили.

[Константин Китманов]

@gwer, да, забыл упомянуть, сумма чисел будет 100 (100%).

[Константин Китманов]

@gwer спасибо, попробую релизовать.

[vans239]

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

[Владлен Грачев]

@vans239, а даст ли перебор результат лучший, чем такого рода выборка? Если бы результатом были множества с разной мощностью, этот метод бы стоило однозначно отбросить. А в данном случае, мне не приходят в голову навскидку расклады, при которых метод не решит задачу.
PS: могу ошибаться, сильно думать сейчас лень.

[Константин Китманов]

@vans239 Array#sort довольно быстрый.

Answer 4

[Mrrl]

Отсортировать в порядке убывания, потом первые два элемента положить в разные кучки, а каждый следующий - в ту из кучек, где сумма на данный момент меньше. Работать будет не всегда (например, 25,25,20,20,9,1), зато не требует перебора.