Задача о максимальном произведении разбиения¶

Question

Дан положительный целый \(n\). Требуется разложить его в сумму как минимум двух положительных целых чисел и найти максимально возможное произведение всех полученных чисел, как показано на рисунке ниже.

Предположим, что мы разбили \(n\) на \(m\) целочисленных множителей, где \(i\)-й множитель обозначим через \(n_i\), то есть

\[ n = \sum_{i=1}^{m}n_i \]

Цель задачи - найти максимальное произведение всех целочисленных множителей, то есть

\[ \max(\prod_{i=1}^{m}n_i) \]

Нужно понять: каким должно быть число частей \(m\) и какими должны быть значения каждого \(n_i\)?

Определение жадной стратегии¶

Из опыта известно, что произведение двух целых чисел часто больше их суммы. Предположим, что мы выделяем из \(n\) множитель \(2\), тогда произведение равно \(2(n-2)\). Сравним это выражение с \(n\):

\[ \begin{aligned} 2(n-2) & \geq n \newline 2n - n - 4 & \geq 0 \newline n & \geq 4 \end{aligned} \]

Как показано на рисунке ниже, когда \(n \geq 4\), выделение множителя \(2\) увеличивает произведение. Это означает, что все целые числа, большие либо равные \(4\), следует продолжать разбивать.

Жадная стратегия 1: если в схеме разбиения присутствует множитель \(\geq 4\), то его нужно дальше разбивать. В конечной схеме разбиения должны остаться только множители \(1\), \(2\), \(3\).

Теперь подумаем, какой множитель является наилучшим. Среди \(1\), \(2\), \(3\) очевидно худшим является \(1\), потому что всегда выполняется \(1 \times (n-1) < n\), то есть выделение \(1\) уменьшает произведение.

Как показано на рисунке ниже, при \(n = 6\) имеем \(3 \times 3 > 2 \times 2 \times 2\). Это означает, что выделять \(3\) выгоднее, чем выделять \(2\).

Жадная стратегия 2: в схеме разбиения должно быть не более двух множителей \(2\). Потому что три двойки всегда можно заменить двумя тройками и получить большее произведение.

Итак, получаем следующую жадную стратегию.

Для заданного целого \(n\) непрерывно выделять из него множитель \(3\), пока остаток не станет равным \(0\), \(1\) или \(2\).
Если остаток равен \(0\), это означает, что \(n\) кратно \(3\), и больше ничего делать не нужно.
Если остаток равен \(2\), дальнейшее разбиение не требуется, его нужно сохранить.
Если остаток равен \(1\), то поскольку \(2 \times 2 > 1 \times 3\), последний множитель \(3\) следует заменить на \(2\).

Код реализации¶

Как показано на рисунке ниже, нам не нужен цикл, чтобы выполнять разбиение числа. Можно использовать целочисленное деление, чтобы получить число троек \(a\), и операцию взятия остатка, чтобы получить остаток \(b\). Тогда имеем:

\[ n = 3 a + b \]

Обратите внимание, что для граничного случая \(n \leq 3\) необходимо выделить множитель \(1\), и тогда произведение равно \(1 \times (n - 1)\).

[file]{max_product_cutting}-[class]{}-[func]{max_product_cutting}

Временная сложность зависит от того, как в языке программирования реализовано возведение в степень. Если взять Python, то обычно используются три распространенные функции для вычисления степени.

Оператор ** и функция pow() имеют временную сложность \(O(\log⁡ a)\).
Функция math.pow() внутри вызывает функцию pow() из библиотеки C, выполняющую возведение в степень с плавающей точкой, и ее временная сложность равна \(O(1)\).

Переменные \(a\) и \(b\) занимают дополнительную память постоянного размера, поэтому пространственная сложность равна \(O(1)\).

Доказательство корректности¶

Используем доказательство от противного и рассмотрим только случай \(n \geq 4\).

Все множители \(\leq 3\): предположим, что в оптимальной схеме разбиения существует множитель \(x \geq 4\). Тогда его можно дальше разложить в \(2(x-2)\) и получить большее или равное произведение. Это противоречит предположению.
Схема разбиения не содержит \(1\): предположим, что в оптимальной схеме присутствует множитель \(1\). Тогда его можно объединить с другим множителем и получить большее произведение. Это противоречит предположению.
Схема разбиения содержит не более двух \(2\): предположим, что в оптимальной схеме присутствуют три двойки. Тогда их можно заменить двумя тройками и получить большее произведение. Это противоречит предположению.