跳转至

15.4   最大切分乘积问题

Question

给定一个正整数 \(n\) ,将其切分为至少两个正整数的和,求切分后所有整数的乘积最大是多少,如图 15-13 所示。

图 15-13   最大切分乘积的问题定义

图解 15-13:最大切分乘积的问题定义

在总和固定的条件下,选择切分段数和各段大小,使乘积最大。

最大切分乘积问题要求:给定一个正整数 n(n ≥ 2),将其拆分为 m 个(m ≥ 2)正整数的和 n = n₁ + n₂ + … + nₘ,最大化这 m 个切分因子的乘积 n₁ × n₂ × … × nₘ。

画面是一张符号示意条形图:上方一整条灰色长条标注为总长度 n;下方一条等长的彩色分段条被竖直虚线切分为多段,从左到右依次标注为 n₁、n₂、n₃、…、nₘ₋₂、nₘ₋₁、nₘ,左右两端对齐虚线表明各段长度之和仍等于 n;图下方列出目标表达式:“输入整数 n,求 max(n₁ × n₂ × n₃ × … × nₘ₋₂ × nₘ₋₁ × nₘ)”。

这些标签与省略号是表示任意 m 段的通用写法,不限定至少有六段;m 最小可为 2。本图没有指定 n、m 或各段的具体数值,不能由示意宽度推算各段的大小。

假设我们将 \(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\) 的整数都应该被切分。

贪心策略一:如果切分方案中包含 \(\geq 4\) 的因子,那么它就应该被继续切分。最终的切分方案只应出现 \(1\)、\(2\)、\(3\) 这三种因子。

图 15-14   切分导致乘积变大

图解 15-14:切分可使乘积不减

较大的整数因子可以继续切分,使乘积不减。

在最大切分乘积问题中,考察一个整数因子 n 是否还应拆开:比较原因子 n 与拆成 2 和 n - 2 后的乘积。

画面上方为表示长度 n 的灰色长条;下方等长条在左侧切出一段绿色短条“2”,右侧剩余蓝色长条标注“n - 2”,分界处有竖直虚线对齐;图下方给出推导结论:“当 n ≥ 4 时,恒有 2(n - 2) ≥ n,因此最终切分方案只应存在 1, 2, 3 因子”。

2(n - 2) - n = n - 4,所以 n = 4 时相等,n > 4 时严格增大。反复拆分大于等于 4 的因子不会损失乘积,因此存在一种只含 1、2、3 的最优方案;这不表示所有最优方案都不能保留 4。

接下来思考哪个因子是最优的。在 \(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\) 总是可以替换为两个 \(3\) ,从而获得更大的乘积。

图 15-15   最优切分因子

图解 15-15:将三个 2 换成两个 3

比较总和同为 6 的两种局部切分:三个 2 与两个 3。

在最优切分只需考虑因子 1、2、3 的基础上,本图讨论已经包含三个 2 的方案;其余因子保持不变。

画面顶层为总长 n 的灰色整条;中层左侧连续排列三个蓝色的“2”(总长 6),右侧接灰色剩余段;底层仅画出左侧同样长度 6 的区间,将它替换为两个紫色的“3”;右侧灰色余段只在中层绘出,不参与变换。中间一支向下的灰色实心箭头标示从“三个 2”到“两个 3”的转化,图下方标注“当存在三个 2 时,应该贪心地转化为两个 3”。

三个 2 的乘积为 8,两个 3 的乘积为 9,二者总和都是 6。设其余正整数因子的乘积为 P;没有其余因子时取 P = 1。局部替换使整体乘积由 8P 增为 9P,因此最优方案中最多保留两个 2。这是对图示局部变换的推导。

综上所述,可推理出以下贪心策略。

  1. 输入整数 \(n\) ,从其不断地切分出因子 \(3\) ,直至余数为 \(0\)、\(1\)、\(2\) 。
  2. 当余数为 \(0\) 时,代表 \(n\) 是 \(3\) 的倍数,因此不做任何处理。
  3. 当余数为 \(2\) 时,不继续划分,保留。
  4. 当余数为 \(1\) 时,由于 \(2 \times 2 > 1 \times 3\) ,因此应将最后一个 \(3\) 和余数 \(1\) 替换为两个 \(2\) 。

2.   代码实现

如图 15-16 所示,我们无须通过循环来切分整数,而可以利用向下整除运算得到 \(3\) 的个数 \(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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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 为 3 的个数,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   最大切分乘积的计算方法

图解 15-16:最大切分乘积的计算方法

通过整除与取模将 n 写成 3×a+b 并按余数分类调整切分;边界 n=2、3 须单独满足至少切分为两段的要求。

给定整数 n ≥ 2,要求将其切分为至少两个正整数之和,并在总和固定为 n 的条件下最大化各段乘积。

既然贪心最优策略是尽可能多地切出因子 3,代码实现便无需循环逐段切分,而是直接利用向下整除 a = n // 3 与取模 b = n % 3,一步算出可切出的 3 的个数 a 与余数 b。

图中把总长为 n 的整条分解为 a 个长度为 3 的段与一段“余数 b”,下方给出代数恒等式 n = 3 × a + b(其中 a = n // 3,b = n % 3,余数 b 只可能是 0、1、2)。注意图中将“余数 b”画在左侧仅作符号分解示意,并未指定具体 n 或 b 的数值,也不代表按从左到右顺序执行切分。 蓝色的 3 段之间用省略号表示未逐一画出的同类分段。

下表由正文与代码补充,图中没有画出这五种分类结果。边界 n = 2、3 必须至少切成两段,不能直接保留整个 n。

当 n ≥ 4 且 b = 1 时,a ≥ 1,至少有一个 3 可与余数 1 重组。把这两段换成 2 + 2,总长仍为 4,局部乘积由 3 提升为 4;因子 3 从 a 个减为 a−1 个,得到 3^(a−1) × 2 × 2。

由正文与代码给出的分类计算规则
适用条件切分或重组最大乘积
n=21+11
n=31+22
n≥4,b=0a 个 33^a
n≥4,b=1a−1 个 3 与两个 2;一个3和余数1改成2+23^(a−1)×2×2
n≥4,b=2a 个 3 与一个 23^a×2

图中的“余数 b”仅表示商余分解:b = 0 时没有余段,b = 2 时可保留为一个因子,b = 1 时要按表中规则重组,不能把 0 当作切分因子。

时间复杂度取决于编程语言的幂运算的实现方法。以 Python 为例,常用的幂计算函数有三种。

  • 运算符 ** 和函数 pow() 的时间复杂度均为 \(O(\log⁡ a)\) 。
  • 函数 math.pow() 内部调用 C 语言库的 pow() 函数,其执行浮点取幂,时间复杂度为 \(O(1)\) 。

变量 \(a\) 和 \(b\) 使用常数大小的额外空间,因此空间复杂度为 \(O(1)\) 。

3.   正确性证明

使用反证法,只分析 \(n \geq 4\) 的情况。

  1. 所有因子 \(\leq 3\) :假设最优切分方案中存在 \(\geq 4\) 的因子 \(x\) ,那么一定可以将其继续划分为 \(2(x-2)\) ,从而获得更大(或相等)的乘积。这与假设矛盾。
  2. 切分方案不包含 \(1\) :假设最优切分方案中存在一个因子 \(1\) ,那么它一定可以合并入另外一个因子中,以获得更大的乘积。这与假设矛盾。
  3. 切分方案最多包含两个 \(2\) :假设最优切分方案中包含三个 \(2\) ,那么一定可以替换为两个 \(3\) ,乘积更大。这与假设矛盾。
欢迎在评论区留下你的见解、问题或建议