CODEWITHSUNDEEP
pythonalgorithmnumbers
user2936448
user2936448

Reputation: 339

Calculate the closest summation to X using a list of numbers

I have a list of numbers

[850, 1300, 810, 590, 590, 910, 480, 1170, 430, 530, 295, 970, 560, 410, 570, 680, 180, 180, 400, 1040]

I want to give the function an integer argument and have it return the closest number possible by summing numbers in the list, and telling me which numbers it used to achieve this.

For example, I give it the number 3255, and it will spit out something like

1300, 810, & 1170 sum to 3280

(I'm not sure if this is the actual closest combination from this example, just showing how it should work)

Upvotes: 0

Views: 161

Answers (2)

Ashok
Ashok

Reputation: 93

The following is the pseudo code that executes in better complexity than brute force

Assuming the input array is arr[], there is a stack to store output

recurse(n, index)
{
    int temp = n; int ind = index;
    while(ind<arr.length)
        if(arr[ind]>n)
            ind++;
        else
            temp = temp - arr[ind];
            stack.push(temp);
            if(temp==0)
                return true;
            result = recurse(temp,ind+1);
            if(result is false)
                temp = n; stack.pop();
                ind++;
            else
                break;
    if(ind==arr.length) then return false
}
print stack

Example: If the array is the following 11 9 8 7 5 and you need to find 26 then it executes as follows

recurse(26,0) 26-11 -> recurse(15,1) since 26-11 = 15; pushes 11 in stack recurse(15,1) 15-9 -> recurse(6,2) since 15-9 = 6; pushes 9 in stack recurse(6,2) 6-5 -> recurse(1,4) pushes 5 in stack recurse(1,4) returns false because there is no element smaller than 1 pops 5 from stack since there is no element smaller than 6 other than 5, pops 9 from stack now it computes 15-8 = 7 recurse(7,3), pushes 8 in stack recurse(7,3) pushes 7 in stack returns true

Finally it prints stack 11, 8, 7 where 11 + 8 + 7 = 26

Upvotes: 0

Kyle G
Kyle G

Reputation: 1038

If you just want to brute-force the problem, use a modified powerset recipe from itertools:

import itertools as it

def powerset(iterable):
    "powerset([1,2,3]) --> (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return it.chain.from_iterable(it.combinations(s, r) for r in range(1, len(s)+1))

def f(n, lst):
    return min((abs(n-sum(i)), i) for i in powerset(lst))[1]

This approach doesn't work for initial lists much larger than your example list though because powersets grow exponentially.

Upvotes: 1

Related Questions