求解无余数拆分最大组合数的算法 现有双循环方案如何提速

核心思路 #

我们的目标是凑出总高度h时，让两种砖块的总使用个数最大。因为单个砖块的高度越小，相同总高度下能凑出的砖块数就越多，因此总个数最大的组合，一定是优先尽可能多使用高度更小的砖块，只在剩下的高度无法被小砖块整除时，才少量替换为大砖块。
基于这个逻辑，完全不需要嵌套遍历所有可能的砖块组合：

• 先把两个砖块高度排序，记较小值为s，较大值为l
• 我们只需要从小到大尝试大砖块的使用个数k，直到剩下的高度remain = h - k*l 满足两个条件：数值非负、且能被小砖块s整除
• 因为k越小，意味着用的大砖块越少、小砖块越多，总个数自然最大，第一个找到的符合条件的k，就是我们要的最优解

现有双循环实现的效率瓶颈 #

现有实现的思路方向是对的，但存在大量冗余计算：

• 外层循环从最多可放的小砖块数量开始倒序遍历，本质上是在寻找包含最多小砖块的组合，逻辑方向没问题
• 但内层循环会遍历所有可能的大砖块数量j，逐次判断a*i +b*j 是否等于h，这一步完全没必要：对每个外层遍历的i，剩下需要凑的高度是remain = h - i*a，根本不需要循环j，直接判断remain能否被b整除即可，能整除的话j=remain//b，就是符合要求的解
• 这种写法的时间复杂度是O((h/a)*(h/b))，当目标高度h很大时，循环次数会爆炸。比如h=1e6、a=1、b=2的场景，需要执行近5e11次判断，完全没有实用性。

优化后的实现 #

我们不需要跟着h的大小走循环，最多只需要遍历s次（也就是较小砖块的高度值）就可以判断是否有解：

h, a, b = 21, 3, 5
s, l = sorted([a, b])
# 最多遍历s次，因为模s的余数只有s种可能，超过s次必然是重复循环
for k in range(s):
    remain = h - k * l
    if remain >= 0 and remain % s == 0:
        total = remain // s + k
        print(total)
        exit()

效率对比 #

• 优化后的代码循环次数完全不随h的大小变化，哪怕h是1e18的量级，只要s是个较小的数，最多遍历s次就能出结果。比如s=3的场景，最多3次循环就能得到答案，和原代码需要遍历几十万次相比，效率提升是数量级级别的。
• 如果需要进一步极致性能，还可以通过扩展欧几里得算法直接求解线性同余方程，在O(log min(a,b))的时间内直接算出符合条件的k值，完全不需要循环，适合a、b本身也很大的场景。
• 如果遍历完s次都没找到满足条件的解，就说明不存在无余数拆分的组合，直接无输出即可，完全符合需求。

举个实际验证的例子：h=21，a=3，b=5，s=3，l=5
第一次循环k=0时，remain=21，刚好能被3整除，直接算出总个数7，连一次多余循环都没有，和示例的正确结果完全一致。

内容的提问来源于stack exchange，提问作者user13566332