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];
    }

[5710xIa]

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

[JxtGTG]

感谢老师们的讲解，但小白有个问题想请教一下。虽然分3和分2最后的因子都是3，2，1，但在思考的过程中，为什么在得到分2的条件后，没有考虑n>=4.5（或者n>=5）就分3的情况，直接考虑后续33和22*2的大小问题。这篇讲解中是因为分3和分2最后都是3，2，1为因子所以省略了吗，还是有什么别的逻辑思路我没有考虑到。老师可不可以有时间的时候帮我解答一下。谢谢！

[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 的因子都应该分解。

[WalkerInAI]

均值不等式的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）特殊处理即可。
不知道这样理解算符合直觉吗。

[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；

[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]

确实严谨

[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