整数拆分最大乘积问题Hello Algo 中的贪心策略推导、实现与正确性证明【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo导读本文围绕《Hello Algo》贪心算法章节中的“最大切分乘积Maximum Product Cutting问题”展开完整讲解问题建模、贪心策略的两步推导只保留因子 1/2/3、最多两个 2、基于n 3a b的常数级算法实现并给出严谨的反证法正确性证明。结合 codes 下 Python/Java/Go/C/JavaScript 等 16 种语言的真实实现与 单元测试读者可同时掌握“如何从直觉推导贪心策略”与“如何证明贪心策略正确”的完整方法论。问题定义切分整数并使乘积最大!!! question给定一个正整数 $n$将其切分为**至少两个**正整数的和求这些整数乘积的最大值。设 $n$ 被切分为 $m$ 个整数因子第 $i$ 个因子记为 $n_i$即$$ n \sum_{i1}^{m} n_i $$本问题的优化目标为求全部整数因子的最大乘积$$ \max\left(\prod_{i1}^{m} n_i\right) $$我们同时需要回答两个子问题应当切成多少份 $m$每一份 $n_i$ 各取何值例如下图所示直观上 $n 5$ 可以切分为 $1 4$乘积 $4$或 $2 3$乘积 $6$后者更优。贪心策略的推导本问题的贪心策略可以从两个递进的关键观察中推导出来其核心直觉源于把大数拆小往往能带来乘积增大。推导 1不小于 4 的因子都应当继续切分经验上两个整数的乘积往往大于它们的和。假设我们从 $n$ 中切出一个因子 $2$则剩余部分为 $n - 2$所得乘积为 $2(n-2)$。将该乘积与原数 $n$ 比较$$ \begin{aligned} 2(n-2) \geq n \ 2n - 4 \geq n \ n \geq 4 \end{aligned} $$也就是说当 $n \geq 4$ 时切出一个 2 会让乘积增大而切出 2 后剩余 $n-2$ 如果仍不小于 4 还可以继续切直到切不动为止。由此得出贪心策略一若切分方案中包含 $\geq 4$ 的因子就应继续将其切分。因此最终的切分方案中只能出现因子 $1$、$2$、$3$。推导 2在 1、2、3 中3 是最优因子接下来在三个候选因子 $1$、$2$、$3$ 中比较优劣1 是最差的因子因为 $1 \times (n-1) n$ 恒成立切出 1 反而会减小乘积。3 优于 2当 $n 6$ 时$3 \times 3 9 2 \times 2 \times 2 8$。更一般地由于 $3 \times 3 9 2 \times 2 \times 2 8$三个 2 总可以用两个 3 替换并得到更大的乘积。由此得出贪心策略二切分方案中 2 的个数至多为两个因为一旦出现三个 2即可用两个 3 替换来增大乘积。汇总为可执行的四条规则综合两条推导可得到如下贪心切分规则输入整数 $n$不断切出因子 $3$直到余数为 $0$、$1$ 或 $2$余数为 $0$ 时说明 $n$ 是 3 的倍数无需额外处理余数为 $2$ 时不再切分原样保留余数为 $1$ 时由于 $2 \times 2 1 \times 3$把最后一个 $3$ 与剩余的 $1$ 合并替换为两个 $2$。这里的第二条推导是一条典型的“局部修改”证明思路假设切分方案里出现了三个 2把它们整体替换成两个 3 不会影响方案中其它因子却能严格增大总乘积。这种“替换后变优”的论证方式在贪心策略推导中非常常见。算法实现O(1) 时间的一行式公式化写法数学基础n 3a b与直觉不同我们不需要用循环去逐个切分 3。借助整数除法与取模运算即可一步完成令 $a n / 3$整除表示 3 的个数令 $b n % 3$取模表示余数。于是有 $n 3a b$。分类讨论余数 $b$ 即可直接写出答案其中需特别注意边界情况当 $n \leq 3$ 时必须切出一个 1答案退化为 $1 \times (n - 1)$例如 $n 2$ 只能切为 $11$$n 3$ 只能切为 $12$。核心代码实现以下为仓库中 Python 语言的实现位于 codes/python/chapter_greedy/max_product_cutting.pyimport math 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))对照上述分类逻辑代码中共有三种返回值形态与贪心规则一一对应余数 b返回值公式含义$b 0$$3^a$$n$ 是 3 的倍数全部切分为 3$b 2$$3^a \times 2$余数 2 原样保留$b 1$$3^{a-1} \times 2 \times 2$少用一个 3换取两个 216 种语言的同构实现本仓库在codes目录下为几乎所有支持语言都提供了完全同构的实现且函数命名保持一致max_product_cutting/maxProductCutting便于对照阅读面向对象类语言Java、C、C#、Kotlin、Swift脚本与动态语言Python、JavaScript、TypeScript、Ruby、Dart系统级语言C、Go、Rust几种代表性语言的差异仅体现在除法/取幂的语法上例如Java 中整型除法int a n / 3;配合(int) Math.pow(3, a - 1) * 2 * 2见 max_product_cutting.javaGo 中需将幂指数显式转为浮点int(math.Pow(3, float64(a-1))) * 2 * 2见 max_product_cutting.goJavaScript 中需先Math.floor(n / 3)取整再取模见 max_product_cutting.js。复杂度分析取决于语言内置幂运算的实现时间复杂度与所用编程语言的求幂实现方式密切相关。以 Python 为例三种常见求幂方式的复杂度差异很大运算符**与函数pow()的时间复杂度为 $O(\log a)$基于快速幂/二进制指数展开函数math.pow()内部调用 C 库的pow()执行浮点求幂时间复杂度为 $O(1)$。由于 $a \approx n/3$这意味着若使用math.pow()整体算法可在常数时间 $O(1)$内求得答案而使用**或pow()则为 $O(\log n)$——这比任何“逐个切分 3”的 $O(n)$ 循环都要快得多。空间复杂度变量 $a$、$b$ 仅占用常量额外空间因此空间复杂度为 $O(1)$。验证以 n 58 为例仓库各语言的驱动代码统一采用 $n 58$ 进行验证。手动推演$58 3 \times 19 1$即 $a 19$、$b 1$属于余数为 1 的情形答案为 $3^{18} \times 4 1549681956$。该结果可由运行任意一个驱动代码或 Go 单元测试 得到确认。正确性证明反证法三连最后为什么上述贪心策略一定得到全局最优解教材中采用反证法给出严格证明。只需考虑 $n \geq 4$ 的情形$n \leq 3$ 的平凡情形直接枚举即可所有因子都不超过 3。假设最优切分方案中包含因子 $x \geq 4$则可将其进一步切分为 $2(x-2)$得到更大或相等的乘积由 $2(x-2) \geq x$ 当 $x \geq 4$ 时成立与“最优”假设矛盾。切分方案中不包含 1。假设最优方案中包含因子 1则可将其合并进另一个因子得到更大的乘积与“最优”假设矛盾。这与前文贪心推导中“切出 1 会减小乘积”的判断互为印证。切分方案中至多包含两个 2。假设最优方案中包含三个 2则可用两个 3 替换$3 \times 3 9 2 \times 2 \times 2 8$得到更大的乘积与“最优”假设矛盾。综合 1、2、3最优切分方案必然只含因子 3及至多两个 2 与可能的边界余数这正是贪心策略给出的切分方式。因此该问题具备贪心选择性质贪心解即为全局最优解。与贪心算法方法论的整体关联本问题是《Hello Algo》贪心算法章节中典型的“贪心可证最优”案例与章节内另一主角“硬币找零问题”形成鲜明对照硬币找零在部分面额组合下贪心失效需借助动态规划而整数拆分则可通过反证法严格确立贪心选择性质。二者共同诠释了贪心算法的完整求解三步曲——问题分析、确定贪心策略、正确性证明参见 greedy_algorithm.md。若想运行各语言实现可参照codes目录下各语言的构建/运行配置如 C 语言的 CMakeLists.txt、Go 的go test等直接执行驱动代码。延伸思考学完本节后可以尝试以下两个自测方向进一步检验理解深度边界完备性逐一验证 $n 2, 3, 4, 5, 6, 7, 8$ 时算法输出是否与手算一致尤其是 $b 1$ 时“借 3 换两个 2”的处理反证法推广能否将“三个 2 换成两个 3”的论证推广为一般命题——证明对任意 $k \geq 3$因子 3 是“平均效益”最高的切分单元可用每单位整数贡献的 $\ln$ 增量来分析。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考