CODEWITHSUNDEEP
pythonalgorithmdynamic-programming
Marked as Duplicate
Marked as Duplicate

Reputation: 1249

Get a sum using as many numbers in a set as possible

Given three numbers, all of them positive. Two numbers that you may add together and a maximum. I must return the largest amount of numbers I can add together while remaining under or being just at the maximum limit. In other words:

I am provided two numbers n and m, and the sum s. Find largest possible amount that a+b can be, if:

a * n + b * m <= s

I do think that I have a working (yet over-complicated and long) solution if the two numbers add exactly up to the sum, but if there's a remainder then it breaks.

For example, if the two numbers are 3 and 5 and the sum is 54, then the answer is 18.

Upvotes: 1

Views: 121

Answers (1)

Stephen Rauch
Stephen Rauch

Reputation: 49784

The answer will always be the max number of time the smaller of m, n will div into s.

Code:

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

Why:

The answer (a+b) is the raw count of instances of m and n. If you start with the assumption that max_a_plus_b is the number of times the smaller of m, n will div in s. Then taking one less of that factor and one more of the other factor will give the same a+b but a larger s, so the answer is already optimal at that point.

Upvotes: 2

Related Questions