求满足a*n +b*m ≤s的最大a+b值的高效解法咨询

嘿，这个问题其实不用纠结“刚好等于s”的特殊情况，咱们换个思路直接瞄准最大化a+b的目标就行，简单又高效！

核心思路 #

要让a+b最大，本质是在a*n + b*m ≤ s的约束下，尽可能多地累加a和b的数量总和。这里有个实用的优化技巧：枚举其中一个变量的可能取值范围，计算对应另一个变量的最大值，然后记录总和的最大值。

为了减少枚举次数，我们可以选择枚举取值范围更小的那个变量：比如如果n比m大，那s//n的结果肯定比s//m小，这时候枚举a的次数就更少；反之就枚举b。这样整个算法的时间复杂度是O(min(s/n, s/m))，哪怕n和m很大，也能快速算出结果。

示例代码（Python） #

def max_total_ab(n, m, s):
    max_sum = 0
    # 选枚举次数少的变量来循环，提升效率
    if n > m:
        # 枚举b的所有可能取值
        max_b = s // m
        for b in range(max_b + 1):
            remaining = s - b * m
            a = remaining // n
            current_sum = a + b
            if current_sum > max_sum:
                max_sum = current_sum
    else:
        # 枚举a的所有可能取值
        max_a = s // n
        for a in range(max_a + 1):
            remaining = s - a * n
            b = remaining // m
            current_sum = a + b
            if current_sum > max_sum:
                max_sum = current_sum
    return max_sum

举个例子验证 #

比如n=3，m=5，s=20：

• 枚举a从0到6（因为20//3=6）：
  • a=5时，剩余20-15=5，b=1，总和5+1=6
  • a=6时，剩余20-18=2，b=0，总和6+0=6
• 最终最大总和就是6，完全符合预期，不管有没有余数都能正确处理。

为什么这个方法更好？ #

相比你之前只处理“恰好等于s”的复杂逻辑，这个方法：

• 逻辑简单直观，不容易出错
• 自动兼容有余数的情况，不用额外写分支处理
• 效率极高，枚举次数最多也不会超过s//min(n,m)，对于大数值也能快速出结果

内容的提问来源于stack exchange，提问作者Marked as Duplicate