Максимизировать сумму GCD (величайших общих делителей) двудольного раздела? - PullRequest
Новая
       15

Максимизировать сумму GCD (величайших общих делителей) двудольного раздела?

4 голосов
/ 08 июня 2019

Дан массив положительных чисел.Я хочу разделить массив на 2 различных подмножества, чтобы сумма их gcd (наибольший общий делитель) была максимальной.

Пример массива: {6,7,6,7}.

Ответ: Ответдва обязательных подмножества: {6,6} и {7,7};их соответствующие gcd - 6 и 7, их sum = 6+7=13;что является максимально возможным суммированием gcd.

Gcd: Gcd из {8,12} равно {4}, поскольку 4 является наибольшим числом, которое делит 8, а также 12.

Примечание: gcd(X)=Xесли подмножество содержит только один элемент.

Мой подход: путем грубой форсировки я нахожу все возможные подпоследовательности массива, затем я нахожу максимальную сумму, но это не работает, если входразмер больше 30 номеров.Я нахожусь в поисках более эффективного подхода.

Extra (s): максимальный размер любого входного числа составляет 10 ^ 9, ограничение по времени: -1s кажется хорошим, размер ввода может быть таким большим, как 10 ^5

1 Ответ

11 голосов
/ 08 июня 2019

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

Во-первых, давайте проигнорируем возможность появления значений более одного раза.Очевидно, что лучше всего поместить все копии значения в один и тот же набор, поскольку перемещение некоторых из них в другое место может повредить только GCD ( edit: , если только не существует отдельного отдельного значения).Итак, мы предполагаем, что все элементы различны.Кроме того, пусть M будет максимальным значением любого из элементов.

Подумайте так: существует тривиальное решение - взять самый высокий элемент с одной стороны, а все остальные - с другой.«Все остальные» - может иметь GCD 1 (может быть, конечно, выше), поэтому это решение дает вам M + 1.

Любое подмножество ваших входов с более чем одним отдельным элементом не может иметьGCD выше, чем M / 2 (поскольку такой делитель должен быть умножен на другой делитель, который равен по крайней мере 2, чтобы получить исходное значение, которое не выше, чем M).Таким образом, edit: оптимальное решение не может быть составлено из двух наборов с несколькими различными элементами каждый.Это должен быть один элемент против всех других элементов.

Теперь рассмотрим два старших элемента, имеющих значения M и Md для некоторого d.Если мы не выберем ни одного из них в качестве синглтона, они оба будут на стороне большой группы, что означает, что группа имеет GCD не более d (поскольку если g | M и g | Md, то g | d);и вклад синглтона будет не более, чем Md-1.Таким образом, общий балл будет не более M-1, то есть меньше, чем тот, который мы получаем при выборе наибольшего значения. Следовательно, случай, когда либо самое высокое, либо второе по величине (отдельное) значение на входе должно быть в своем собственном наборе.

Поэтому вам необходимо выполнить следующее:

  • Обработать тривиальный случай только одного отдельного значения.
  • В противном случае получить 2 старших элемента;.
  • Вычислить GCD g_0 из всех n-2 младших элемента.
  • Вычислить GCD g_with_highest = GCD (g_0, M) и g_with_second_highest = GCD (g_0, Md).
  • Выберите синглтон, сравнив M + g_with_second_highest с (Md) +g_with_highest.
...