chapter_greedy/max_product_cutting_problem/

[giscus[bot]]

chapter_greedy/max_product_cutting_problem/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_greedy/max_product_cutting_problem/

[Shednandezstore]

Enhanced security

[WhiteRhinos]

动态规划,对比一下就可以看出贪心的效率了

 public static int dpMultiply(int num)
    {
        int[] max = new int[num + 1];
        // 初始化,0和1都无法分割,为0
        max[0] = 0;
        max[1] = 0;

        for (int i = 2; i <= num; i++)
        {
            // 第一次分割长度
            for (int len = 1; len <= i / 2; len++)
            {
                int temp = Math.max(len * (i - len), len * max[i - len]);
                max[i] = Math.max(temp, max[i]);
            }
        }
        return max[num];
    }

[sunshinesDL]

这样求解的时间复杂为 O(n^2)，使用贪心策略一可以将其优化到 O(n) 的

[5710xIa]

我还在想条件不是n >= 4才继续拆分吗？为啥会拆出1来？
结果一看，直接一个pow给解决了!
我明白了一个道理，先学数学，再学算法。🤦‍♂️🤦‍♂️🤦‍♂️🤦‍♂️

[nors1993]

所以数学不好的真不适合做算法~

[JxtGTG]

[commo-n]

n>4，n为奇数，分2余1，n为偶数，分2余0。前者要2+1=3。后者一定可以分出一个222，转为3*3，所以一定要从3开始分。

[krahets]

因为我们在第一步分析出得到结论：超出或等于 4 的因子一定可以继续被切分，以获得更大乘积。

[sumaliqinghua]

求问"假设从n中分出一个因子2，则它们的乘积为 2*(n-2)。我们将该乘积与n作比较："。🤔为啥上来就想到分一个因子2而不是其他的，从而推出n>=4还要继续分的

[krahets]

根据对数学运算的理解，我们认为 n * m > n + m 通常是成立的，且 n 和 m 越大，这个不等式就更有可能成立。从这个角度思考，用因子 2 来分析是最合适的，因为它能覆盖到最广的情况。
如果用更大的因子 3, 4, 5, ... 来分析也行，我们都可以得到一样形式的结论：“当数字大于 n 时，分出因子 m 可以得到更大的乘积”。然而，我们可以对这个大因子继续进行分解，直至发现 2 * 2 = 4 ，即 >= 4 的因子都应该分解。

[LeoooKang]

均值不等式的n维展开...算法和数学结合起来就更有意思啦！

[syutengu]

根据命题“对于任意正整数 m,n>=2 ，均有 m*n>=m+n 成立。”
从最小的2开始逐项尝试，首先得到的结论就是n>=4时既满足。
用3试，可得n>=4.5。
用100试，可得n>=101。
...
那4应该就是用这套方法能得到的（把问题一般化的）临界值了。
即，如果结果里还有大于4的因子，继续拆就是了，保证你结果变大。
然后未满4的特殊情况1,2,3（或者说针对拆到最后的所有特殊零件1,2,3）特殊处理即可。
不知道这样理解算符合直觉吗。

[sunshinesDL]

即，如果结果里还有大于4的因子，继续拆就是了，保证你结果变大。

如果结果中的元素 >= 5 时才继续拆分，4 也属于边界情况；
此外，如果只使用书中的贪心策略一，可以使用 动态规划 求解，献丑贴下代码：

def max_product_cutting_dp(n: int) -> int:
    """正整数切分最大乘积 - 动态规划"""
    # 1. 根据数学证明，n >= 5时，切分所得乘积 > 不切分；因此先考虑 n <= 4 的边界情况：
    if n <= 3:  # 题目规定 n 至少切分为两个正整数；
        return 1 * (n - 1)
    if n == 4:
        return 2 * (n - 2)
    # 使用 DP 框架，先初始化 dp 表并考虑初始状态：
    dp = [1] * (n + 1)
    # 当拆分结果的元素个数 >= 2时，其中的 2,3 不再拆分可以使乘积更大；4 拆不拆结果相同，那就不拆：
    for i in range(2, 5):
        dp[i] = i
    # 2. n >= 5时要继续切分，如何切分呢？
    # 表面看切分方案好像有 n-1 种，但当切分结果中包含 >= 5 的数时，对其继续切分可以使乘积更大，
    # 因此切分的因子只可能是 1 ~ 4，且由于 4 = 2 * 2，故因子只有 1 ~ 3，
    # 由于切分出 1 会使最终的乘积变小，因此只考虑因子 2 ~ 3，
    # 从而得到状态转移方程：dp[n] = max(2 * dp[n-2], 3 * dp[n-3]),
    # 注意，由于不断切分出 2 或 3，最终的切分结果可能剩余 0,1,2，这三个数的 dp 值要提前初始化；
    for i in range(5, n + 1):
        dp[i] = max(2 * dp[i - 2], 3 * dp[i - 3])
    return dp[n]

[sunshinesDL]

需注意的是，上面动态规划的代码，时空复杂度均为 O(n)，明显劣于贪心算法，适合想不到贪心策略二时使用；

[commo-n]

数学这玩意你知道别人是怎么想到一些定理的吗？一样的道理，灵感罢了

[commo-n]

你说的第一句怎么说呢，数学最忌讳这么说了。

…

根据对数学运算的理解，我们认为 n * m > n + m 通常是成立的，且 n 和 m 越大，这个不等式就更有可能成立。从这个角度思考，用因子 2 来分析是最合适的，因为它能覆盖到最广的情况。如果用更大的因子 3, 4, 5, ... 来分析也行，但最后你还是会发现 2 * 2 = 4 ，即因子 4 也可以再分。

[krahets]

这是一道算法题，而非数学题。
换成数学的说法：对于任意正整数 $n, m >= 2$ ，均有 $n \times m >= n + m$ 成立。

[syutengu]

0. 证明n^2>=2n
   n>=2
   n-2>=0
   (n-2)n>=0
   (n-2)n+2n>=2n
   n^2-2n+2n>=2n
   n^2>=2n

1. m=n时，因为n^2>=2n，所以mn>=m+n

2. m>n时，
   有差值d=m-n(d必>=1),
   mn=(d+n)n=dn+n^2,
   m+n=d+2n，
   因为dn>=d,且n^2>=2n,
   故dn+n^2>=d+2n,即mn>=m+n

3. n>m时，证法同上.

[lwd-coding]

小白尝试证明一下，勿喷哈哈
一个数要么是偶数要么是奇数:
1.偶数可以拆分为 2k ,乘积为 2^k , k>1 ，可证得k为任意数时其 2^k均大于等于2 * k
2.奇数可以拆分为 3k + a (a<3)或者 2k + b (b<2),可证得k为任意数时其3^k * b均大于 2 ^ k * b
因此一个数首先要先看是否时3的倍数,如果是优先拆成3否则拆成2；

[sunshinesDL]

第 2 步的可证得是怎么得到的呢？

[Terran0629]

k神，我有个疑问，三种幂函数的时间复杂度不应该都是O(logn)吗？如果是指调用函数的时间，我直接用内置的pow函数不是比用math库调pow函数更快嘛

[krahets]

不一样，math.pow() 的时间复杂度是 $O(1)$ ，这种疑惑其实最好的方式是自己测一下：

import time
import math

# 设置测试的基数和指数
base = 2
repeat_times = 100000

for exp in [1, 10, 100, 1000]:
    # 测试 **
    start_time = time.time()
    for _ in range(repeat_times):
        base ** exp
    end_time = time.time()
    time_with_operator = end_time - start_time

    # 测试内置 pow 函数
    start_time = time.time()
    for _ in range(repeat_times):
        pow(base, exp)
    end_time = time.time()
    time_with_builtin_pow = end_time - start_time

    # 测试 math.pow
    start_time = time.time()
    for _ in range(repeat_times):
        math.pow(base, exp)
    end_time = time.time()
    time_with_math_pow = end_time - start_time

    print(f'\nbase: {base}, exp: {exp}')
    print(f'Using ** operator: {time_with_operator} seconds')
    print(f'Using builtin pow: {time_with_builtin_pow} seconds')
    print(f'Using math.pow: {time_with_math_pow} seconds')

结果：

# base: 2, exp: 1
# Using ** operator: 0.017894744873046875 seconds
# Using builtin pow: 0.020190000534057617 seconds
# Using math.pow: 0.011484146118164062 seconds

# base: 2, exp: 10
# Using ** operator: 0.02104020118713379 seconds
# Using builtin pow: 0.023619651794433594 seconds
# Using math.pow: 0.01145029067993164 seconds

# base: 2, exp: 100
# Using ** operator: 0.025892257690429688 seconds
# Using builtin pow: 0.028349876403808594 seconds
# Using math.pow: 0.011298894882202148 seconds

# base: 2, exp: 1000
# Using ** operator: 0.054923057556152344 seconds
# Using builtin pow: 0.05742311477661133 seconds
# Using math.pow: 0.011198997497558594 seconds

[Terran0629]

好的 谢谢k神

[SSR-chen]

我的思路是先尝试对半分，然后从（n^2/4-n=0）的解想到了小于等于四都要切分，但没想到替换成3，TUT

[goddog111222]

更严谨的做法应该是将切分的最优整数设为变量x,那么连续做乘法所得到的关于x的函数应该是x的n/x次方，转换为e的幂级数e的n(lnx/x）次方，由于取正整数，那么x=3的时候是最接近lnx/x的极值点的取值，e的幂级数又是递增函数，所以x = 3是最好的因子。

[goddog111222]

个人觉得哈，不对的话也可以指出

[b1ackmarket]

确实严谨

[sunshinesDL]

更严谨的做法应该是将切分的最优整数设为变量x,那么连续做乘法所得到的关于x的函数应该是x的n/x次方，转换为e的幂级数e的n(lnx/x）次方，由于取正整数，那么x=3的时候是最接近lnx/x的极值点的取值，e的幂级数又是递增函数，所以x = 3是最好的因子。

很好的证明，
不过最后两步，是否应该先证明 e的幂级数是递增函数，再证明 x 取正整数时，3 最接近该函数的极值点；

[Doggod727]

更严谨的做法应该是将切分的最优整数设为变量x,那么连续做乘法所得到的关于x的函数应该是x的n/x次方，转换为e的幂级数e的n(lnx/x）次方，由于取正整数，那么x=3的时候是最接近lnx/x的极值点的取值，e的幂级数又是递增函数，所以x = 3是最好的因子。

很好的证明， 不过最后两步，是否应该先证明 e的幂级数是递增函数，再证明 x 取正整数时，3 最接近该函数的极值点；

谢谢指出我的问题。这里是因为e^x次方是递增函数，而lnx/x 是一个先增后减函数，所以e^n(lnx/x)的单调性和lnx/x的单调性相同，而lnx/x在实数域上的极大值点是x = e, 并且我们所求的x的取值范围是自然数，自然就考虑x = 2， 和 x = 3 的情况了，最后简单比较一下，是x = 3为可取点。之前没给主要是lnx/x这个函数比较常见，就没有给出详细说明。

[PotatoSmith]

“这说明大于等于4的整数都应该被切分”， 先分析出子问题

[Mrstarer]

在考虑只分一次时，分1就变小。分的数x全一样时用函数画图分析可得n大于e时分的数乘积才能变大，且x大于e，x取3能使乘积最大。n小于4不够分，n=4分一个x=3会出现1变小，发现lnx/x函数在2和4的值一样，故选择妥协不要3了，选择两个2起码不变小，n=5分一个3虽然没满足分的数全为3，不过剩下的2起码不是1，能变大。从而分解出子问题。

[BK-Go-Python]

这里有点蒙，先看评论区

[BK-Go-Python]

def maxProduct(n: int) -> int:
# 特殊情况处理
if n == 2:
return 1 # 2 = 1 + 1, 乘积为 1
if n == 3:
return 2 # 3 = 1 + 2, 乘积为 2

# 最大乘积初始化为 1
product = 1

# 对 n 进行拆分
while n > 4:
    product *= 3
    n -= 3

# 剩下的 n <= 4，直接乘上
product *= n

return product

[sunshinesDL]

首先，如果用循环，时间复杂度就变为 O(n)了；
其次，代码中：

剩下的 n <= 4，直接乘上

有误，当最终剩下 0 和 1 时，需要特殊处理的。

[jceng574]

对于正整数 n，其各部分之和为 n，乘积最大时（在连续情况下）各部分应尽量相等。根据均值不等式（AM–GM不等式），当 k 个正数的和固定时，它们的乘积在这 k 个数全部相等时达到最大值。

如果允许实数，则最佳划分的每个数为 n/k，使得乘积
𝑃
(
𝑘
)

(
𝑛
𝑘
)
𝑘
P(k)=(
k
n
​
)
k
。对 k 取连续变量时，对数函数
ln
⁡
𝑃
(
𝑘
)

𝑘
(
ln
⁡
𝑛
−
ln
⁡
𝑘
)
lnP(k)=k(lnn−lnk) 在 k = n/e 时达到最大值，且 e ≈ 2.718。

由于要求整数划分，我们只能选取接近 e 的整数。比较 2 与 3，显然 3 更接近 e，且 3 大于 2，因此在大多数情况下，尽可能多地使用 3 会使乘积最大。

[jceng574]

补充一下证明，但发现数学公式好像发不出去

[sunshinesDL]

K大，本节结尾的正确性证明中，

使用反证法，只分析 n >= 3 的情况。

是否应该改为 “只分析 n >= 4 的情况”，因为 n == 3 时，由于题目要求至少将 n 切分为两个正整数，所以此时应该切分为 1 * 2 ，切分方案里是包含 1 的 😁；
此外，对于这句描述：

假设最优切分方案中存在 >= 4 的因子 x ，那么一定可以将其继续划分为 2(x-2) ，从而获得更大的乘积。

最后半句改为“从而获得更大或可替代的乘积”是否更好，因为当切分方案中存在 4 作为因子时，将其划分为 2 * 2，乘积相对划分前是相等的。不过这处改动不影响“所有因子 <= 3” 的结论，因为因子 4 是可以被替代的。
@krahets

[UnknownUserNaN]

私认为以$3$为主要的“切分因子”这一部分应该这么解释比较好：

先去掉正整数的限制，在$m$和各$n_i$均可取正实数时使用AM-GM，可知乘积$\displaystyle \prod_{i=1}^m{n_i}\leq\left(\frac{\sum_{i=1}^m}{m}\right)^m=\left(\frac{n}{m}\right)^m$，该最大值在$\displaystyle \left(\frac{n}{m}\right)^m$在各$n_i$均相等时取得。现设法令该最大值再取得最大，只需令$\displaystyle \left(\frac{n}{m}\right)^m$对$m$求导，得$\displaystyle m=\frac{n}{e}$为该函数的最大值点，此时最大值为$\displaystyle e^{\frac{n}{e}}$，各$n_i$应当都取为$e$。

有了上面正实数情况下的指引，我们不难猜测，正整数情况下的最优解就在上面的实数解附近。

• 当各$n_i$均可取正实数时，各$n_i$应当都取$e$。现在各$n_i$只能取正整数，那么各$n_i$应当取$e$附近的两个正整数，也就是$2$和$3$。也就是说，只有在$n_i$只取$2$或$3$时，我们才有可能取得最大乘积。
• 当$m$可取正实数时，应当有$\displaystyle m=\frac{n}{e}$。现在$m$只能取正整数，于是我们考虑距离$\displaystyle m=\frac{n}{e}$最近的两个数$\displaystyle m=\frac{n}{3}$和$\displaystyle m=\frac{n}{2}$，它们分别对应将$n$全划分成$3$和$2$的情况。当$\displaystyle m=\frac{n}{3}$时，乘积为$\displaystyle 3^{\frac{n}{3}}$；当$\displaystyle m=\frac{n}{2}$时，乘积为$\displaystyle 2^{\frac{n}{2}}$。我们设法比较这两者的大小，于是考虑作商，发现$\displaystyle \frac{3^{\frac{n}{3}}}{2^{\frac{n}{2}}}=\left(\frac{\sqrt[3]{3}}{\sqrt2}\right)^n>1$。这说明将$n$全划分成$3$的做法要比全划分成$2$的做法更能得到更大的乘积。但注意到上面的$\displaystyle m=\frac{n}{3}$和$\displaystyle m=\frac{n}{2}$并不一定是正整数，因此上面只能说明一种“趋势”，也就是尽可能多地划分$3$的做法要比尽可能多地划分$2$的做法更倾向于把乘积扩大。

有了这两条准则，后面就跟正文中的做法大同小异了。我们“贪心”地在$n$中划分出尽可能多的$3$，然后考察除$3$后的余数：

• 若余数为$0$，此时所有$n_i$均为$3$，满足上述两条结论。此时取得最大乘积$\displaystyle 3^{\frac{n}{3}}$。
• 若余数为$1$，此时除了最后一个$n_i$为$1$外，其余$n_i$均为$3$。但这个“$1$”违反了第一条结论，于是我们把最后一个"$1$"与它旁边的”$3$“合起来，重新划分为两个"$2$”。此时取得最大乘积为$\displaystyle 3^{\lfloor\frac{n}{3}\rfloor-1}\times4$。
• 若余数为$2$，此时除了最后一个$n_i$为$2$外，其余$n_i$均为$3$。此时取得最大乘积$\displaystyle 3^{\lfloor\frac{n}{3}\rfloor}\times2$。

---

最后，值得一提的是，上面推理得到第二条结论的过程不够严谨。我们实际上不应该考察$\displaystyle m=\frac{n}{3}$和$\displaystyle m=\frac{n}{2}$，因为这两者有可能不为整数，而应当考察两个最靠近$\displaystyle \frac{n}{e}$的整数$\displaystyle m=\lfloor\frac{n}{e}\rfloor$ 和$\displaystyle m=\lceil\frac{n}{e}\rceil$。但要这么做的话，后面的结论推导会变得相当复杂。