算法学习笔记（7.3）-贪心算法（最大切分乘问题）
目录
##问题描述
##问题思考
##贪心策略确定
##代码实现
##时间复杂度
##正确性验证
##问题描述
给定一个正整数 𝑛 ，将其切分为至少两个正整数的和，求切分后所有整数的乘积最大是多少
##问题思考
假设我们将 𝑛 切分为 𝑚 个整数因子，其中第 𝑖 个因子记为 𝑛𝑖 ，即
本题的目标是求得所有整数因子的最大乘积，即
我们需要思考的是：切分数量 𝑚 应该多大，每个 𝑛𝑖 应该是多少？
##贪心策略确定
我们假设从n中分出一个最小的因子2，则它们的乘积为2 * (n - 2),我们将该乘积与n进行比较得到一个重要结论：
当n≥4的时候，切分出来一个2后乘积会变大，这就说明大于等于4的整数都应该被切分出来。
##贪心策略1
如果切分方案中包含≥4因子，那么它就应该被继续切分。最终的切分方案只应出现1，2，3者三种因子。
这是我们就要思考选择什么因子会使结果达到最优解，1可以直接舍弃考虑。
当n = 6时，3*3>2*2*2，说明因子3比因子2更优。
##贪心策略2
在切分方案中，最多出现两个2.因为3个2总可以替换成2个3，获得最优的更大乘积。
综上所述，可推理出以下贪心策略。
- 输入整数 𝑛 ，从其不断地切分出因子 3 ，直至余数为 0、1、2 。
- 当余数为 0 时，代表 𝑛 是 3 的倍数，因此不做任何处理。
- 当余数为 2 时，不继续划分，保留。
- 当余数为 1 时，由于 2×2>1×3 ，因此应将最后一个 3 替换为 2 。
##代码实现
#python代码示例 import math def max_product_cutting(n) :if n <= 3 :return 1 * (n - 1) a = n // 3b = n % 3if b == 1 :return int(math.pow(3,a-1)) * 2 * 2if b == 2 :return int(math.pow(3,a)) * 2return int(math.pow(3,a))//c++代码示例 int maxProductCutting(int n) {if (n <= 3){return 1 * (n - 1) ; } int a = n / 3 ;int b = n % 3 ;if (b == 1){return (int)pow(3,a-1) * 2 * 2 ;}if (b == 2){return (int)pow(3,a) * 2 ;}return (int)pow(3,a) ; }
##时间复杂度
时间复杂度取决于编程语言的幂运算的实现方法。以 Python 为例，常用的幂计算函数有三种。
- 运算符
**和函数pow()的时间复杂度均为 𝑂(log𝑎) 。- 函数
math.pow()内部调用 C 语言库的pow()函数，其执行浮点取幂，时间复杂度为 𝑂(1) 。变量 𝑎 和 𝑏 使用常数大小的额外空间，因此空间复杂度为 𝑂(1) 。
##正确性验证
使用反证法，只分析 𝑛≥3 的情况。
- 所有因子 ≤3 ：假设最优切分方案中存在 ≥4 的因子 𝑥 ，那么一定可以将其继续划分为 2(𝑥−2) ，从而获得更大的乘积。这与假设矛盾。
- 切分方案不包含 1 ：假设最优切分方案中存在一个因子 1 ，那么它一定可以合并入另外一个因子中，以获得更大的乘积。这与假设矛盾。
- 切分方案最多包含两个 2 ：假设最优切分方案中包含三个 2 ，那么一定可以替换为两个 3 ，乘积更大。这与假设矛盾。