CODEWITHSUNDEEP
pythonarrayssum
Sean O'Connor
Sean O'Connor

Reputation: 168

Calculating the least amount of numbers needed from an array to sum to a specific number

I am having an issue where I have been given an array of numbers [1,3,5] and need to find the least amount of numbers that could add to a specific number. Each number has a weight and I need to calculate the most efficient. For example if the number was 6 I would need to use [5,1] instead of [3,3] as 5 has a greater importance. In the case of 12 it would be [5,5,1,1] instead of [3,3,3,3]

I have already tried implementing dictionaries and arrays but the problem solving part is what I am having trouble with.

Upvotes: 0

Views: 674

Answers (2)

Thierry Lathuille
Thierry Lathuille

Reputation: 24234

A valid way to do it, not relying on the presence of 1 in the list, is to try to use as many of the largest numbers as possible, and recursively try to obtain the remainder:

If no solution can be found, the function will return None

def solve(numbers, target):
    '''Return a list of the largest of numbers whose sum is target, 
    None if impossible'''

    if not numbers:
        return None

    # make sure that numbers is sorted
    numbers = list(sorted(numbers))
    # get the largest number and remove it from the list
    largest = numbers.pop()
    # we start with as many times the largest number as possible
    quotient, remainder = divmod(target, largest)
    # did we reach the target?
    if remainder == 0:
            return [largest] * quotient

    # if not, try with a deacreasing number of times the largest    
    # (including 0 times)
    for n in range(quotient, -1, -1):
        remainder = target - n * largest
        # and recursively try to obtain the remainder with the remaining numbers
        solution = solve(numbers, remainder)
        if solution:
            return [largest] * n + solution
    else:
        return None

Some tests:

solve([1, 3, 5], 12)
# [5, 5, 1, 1]

solve([3, 5], 12) # no 1, we have to use smaller numbers
# [3, 3, 3, 3]

solve([7, 3, 4], 15)
# [7, 4, 4]

solve([3, 4], 5) # Impossible
# None

Upvotes: 2

ofthegoats
ofthegoats

Reputation: 295

Keep looping, until n = 0, by taking away the largest number, then smaller numbers if n < 0.

As pointed out by Thierry Lathuille, This will probably not work if there is no 1 in your array. If that is the case, you might want to fiddle with the if n < 0 lines.

n = int(input())
a = [1, 3, 5]
ans = []
while n > 0:
    n -= max(a)
    if n == 0:
        ans.append(max(a))
        break
    if n > 0:
        ans.append(max(a))
    if n < 0:
        n += max(a)
        a.pop(a.index(max(a)))

print(ans)

Upvotes: 0

Related Questions