Перейти к содержанию

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

Question

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

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

Рисунок 15-13   Определение задачи о максимальном произведении разбиения

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

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

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

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

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

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

Из опыта известно, что произведение двух целых чисел часто больше их суммы. Предположим, что мы выделяем из \(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} \]

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

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

Разбиение увеличивает произведение

Рисунок 15-14   Разбиение увеличивает произведение

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

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

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

Оптимальные множители разбиения

Рисунок 15-15   Оптимальные множители разбиения

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

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

2.   Код реализации

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

\[ n = 3 a + b \]

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

max_product_cutting.py
def max_product_cutting(n: int) -> int:
    """Максимальное произведение разрезания: жадный алгоритм"""
    # Когда n <= 3, обязательно нужно выделить одну 1
    if n <= 3:
        return 1 * (n - 1)
    # Жадно выделить множители 3, где a — число троек, а b — остаток
    a, b = n // 3, n % 3
    if b == 1:
        # Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return int(math.pow(3, a - 1)) * 2 * 2
    if b == 2:
        # Если остаток равен 2, ничего не делать
        return int(math.pow(3, a)) * 2
    # Если остаток равен 0, ничего не делать
    return int(math.pow(3, a))
max_product_cutting.cpp
/* Максимальное произведение разрезания: жадный алгоритм */
int maxProductCutting(int n) {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return (int)pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // Если остаток равен 2, ничего не делать
        return (int)pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return (int)pow(3, a);
}
max_product_cutting.java
/* Максимальное произведение разрезания: жадный алгоритм */
int maxProductCutting(int n) {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return (int) Math.pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // Если остаток равен 2, ничего не делать
        return (int) Math.pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return (int) Math.pow(3, a);
}
max_product_cutting.cs
/* Максимальное произведение разрезания: жадный алгоритм */
int MaxProductCutting(int n) {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return (int)Math.Pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // Если остаток равен 2, ничего не делать
        return (int)Math.Pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return (int)Math.Pow(3, a);
}
max_product_cutting.go
/* Максимальное произведение разрезания: жадный алгоритм */
func maxProductCutting(n int) int {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if n <= 3 {
        return 1 * (n - 1)
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    a := n / 3
    b := n % 3
    if b == 1 {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return int(math.Pow(3, float64(a-1))) * 2 * 2
    }
    if b == 2 {
        // Если остаток равен 2, ничего не делать
        return int(math.Pow(3, float64(a))) * 2
    }
    // Если остаток равен 0, ничего не делать
    return int(math.Pow(3, float64(a)))
}
max_product_cutting.swift
/* Максимальное произведение разрезания: жадный алгоритм */
func maxProductCutting(n: Int) -> Int {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if n <= 3 {
        return 1 * (n - 1)
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    let a = n / 3
    let b = n % 3
    if b == 1 {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return pow(3, a - 1) * 2 * 2
    }
    if b == 2 {
        // Если остаток равен 2, ничего не делать
        return pow(3, a) * 2
    }
    // Если остаток равен 0, ничего не делать
    return pow(3, a)
}
max_product_cutting.js
/* Максимальное произведение разрезания: жадный алгоритм */
function maxProductCutting(n) {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    let a = Math.floor(n / 3);
    let b = n % 3;
    if (b === 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return Math.pow(3, a - 1) * 2 * 2;
    }
    if (b === 2) {
        // Если остаток равен 2, ничего не делать
        return Math.pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return Math.pow(3, a);
}
max_product_cutting.ts
/* Максимальное произведение разрезания: жадный алгоритм */
function maxProductCutting(n: number): number {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    let a: number = Math.floor(n / 3);
    let b: number = n % 3;
    if (b === 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return Math.pow(3, a - 1) * 2 * 2;
    }
    if (b === 2) {
        // Если остаток равен 2, ничего не делать
        return Math.pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return Math.pow(3, a);
}
max_product_cutting.dart
/* Максимальное произведение разрезания: жадный алгоритм */
int maxProductCutting(int n) {
  // Когда n <= 3, обязательно нужно выделить одну 1
  if (n <= 3) {
    return 1 * (n - 1);
  }
  // Жадно выделить множители 3, где a — число троек, а b — остаток
  int a = n ~/ 3;
  int b = n % 3;
  if (b == 1) {
    // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
    return (pow(3, a - 1) * 2 * 2).toInt();
  }
  if (b == 2) {
    // Если остаток равен 2, ничего не делать
    return (pow(3, a) * 2).toInt();
  }
  // Если остаток равен 0, ничего не делать
  return pow(3, a).toInt();
}
max_product_cutting.rs
/* Максимальное произведение разрезания: жадный алгоритм */
fn max_product_cutting(n: i32) -> i32 {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if n <= 3 {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    let a = n / 3;
    let b = n % 3;
    if b == 1 {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        3_i32.pow(a as u32 - 1) * 2 * 2
    } else if b == 2 {
        // Если остаток равен 2, ничего не делать
        3_i32.pow(a as u32) * 2
    } else {
        // Если остаток равен 0, ничего не делать
        3_i32.pow(a as u32)
    }
}
max_product_cutting.c
/* Максимальное произведение разрезания: жадный алгоритм */
int maxProductCutting(int n) {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1);
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    int a = n / 3;
    int b = n % 3;
    if (b == 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return pow(3, a - 1) * 2 * 2;
    }
    if (b == 2) {
        // Если остаток равен 2, ничего не делать
        return pow(3, a) * 2;
    }
    // Если остаток равен 0, ничего не делать
    return pow(3, a);
}
max_product_cutting.kt
/* Максимальное произведение разрезания: жадный алгоритм */
fun maxProductCutting(n: Int): Int {
    // Когда n <= 3, обязательно нужно выделить одну 1
    if (n <= 3) {
        return 1 * (n - 1)
    }
    // Жадно выделить множители 3, где a — число троек, а b — остаток
    val a = n / 3
    val b = n % 3
    if (b == 1) {
        // Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
        return 3.0.pow((a - 1)).toInt() * 2 * 2
    }
    if (b == 2) {
        // Если остаток равен 2, ничего не делать
        return 3.0.pow(a).toInt() * 2 * 2
    }
    // Если остаток равен 0, ничего не делать
    return 3.0.pow(a).toInt()
}
max_product_cutting.rb
### Максимальное произведение разрезания: жадный алгоритм ###
def max_product_cutting(n)
  # Когда n <= 3, обязательно нужно выделить одну 1
  return 1 * (n - 1) if n <= 3
  # Жадно выделить множители 3, где a — число троек, а b — остаток
  a, b = n / 3, n % 3
  # Если остаток равен 1, преобразовать одну пару 1 * 3 в 2 * 2
  return (3.pow(a - 1) * 2 * 2).to_i if b == 1
  # Если остаток равен 2, ничего не делать
  return (3.pow(a) * 2).to_i if b == 2
  # Если остаток равен 0, ничего не делать
  3.pow(a).to_i
end
Визуализация кода

Метод вычисления максимального произведения разбиения

Рисунок 15-16   Метод вычисления максимального произведения разбиения

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

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

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

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

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

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