算法学习笔记（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，获得最优的更大乘积。

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

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

##代码实现

#python代码示例
import math
def max_product_cutting(n) :
    if n <= 3 :
        return 1 * (n - 1) 
    a = n // 3
    b = n % 3
    if b == 1 :
        return int(math.pow(3,a-1)) * 2 * 2
    if b == 2 :
        return int(math.pow(3,a)) * 2
    return 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 的情况。

1. 所有因子 ≤3 ：假设最优切分方案中存在 ≥4 的因子 𝑥 ，那么一定可以将其继续划分为 2(𝑥−2) ，从而获得更大的乘积。这与假设矛盾。
2. 切分方案不包含 1 ：假设最优切分方案中存在一个因子 1 ，那么它一定可以合并入另外一个因子中，以获得更大的乘积。这与假设矛盾。
3. 切分方案最多包含两个 2 ：假设最优切分方案中包含三个 2 ，那么一定可以替换为两个 3 ，乘积更大。这与假设矛盾。