使用尽可能多的数字来获取总和

问题描述 投票:1回答:1

鉴于三个数字,所有这些都是积极的。两个数字,您可以加在一起,最多。我必须返回我可以加在一起的最大数量的数字,同时保持在或仅处于最大限制。换一种说法:

我提供了两个数字n和m,以及总和s。找到a + b可能的最大可能数量,如果:

a * n + b * m <= s

我确实认为如果两个数字完全相加,那么我有一个工作(但过于复杂和冗长)的解决方案,但是如果有一个余数则会中断。

例如,如果两个数字是3和5并且总和是54,那么答案是18。

python algorithm dynamic-programming
1个回答
2
投票

答案将始终是m, n中较小的一部分将分成s的最大时间。

Code:

max_a_plus_b = divmod(s, min(n, m))

Why:

答案(a + b)是mn实例的原始计数。如果你开始假设max_a_plus_bm, n中较小的s div的次数。然后少拿一个因子和另一个因子将给出相同的a+b但是更大的s,所以答案在那时已经是最优的。

© www.soinside.com 2019 - 2024. All rights reserved.