Get the elents whose summ are close to a given number and the number of sum does not exceed the given maximum value

I have a list full of integers(it's not sorted) and I have 2 input: -input no.1 the sum I want to get -input no.2 the maximum number of usable element to get the sum

The sum can't be higher than the given value(input no.1) but can be less by -10. The number of used elements of the list can be equal to or less than the given value(input no.2).

from random import choice
def Diff(li1, li2):
    return (list(list(set(li1)-set(li2)) + list(set(li2)-set(li1))))



def find_the_elements(current_sum, wanted_sum, used_elements, max_number_of_elements, n_o_elements):
    solution = 0
    while solution != 1:

        elemnt=choice(Diff(elemts, used_elements))
        used_elements.append(elemnt)
        current_sum+=elemnt
        n_o_elements+=1
        if max_number_of_elements<=max_number_of_elements and current_sum in wanted_sum:
            return used_elements
        elif n_o_elements>max_number_of_elements or current_sum>wanted_sum.stop:
            return -1
        else:
            x=find_the_elements(current_sum=current_sum, wanted_sum=wanted_sum, used_elements=used_elements, n_o_elements=n_o_elements, max_number_of_elements=max_number_of_elements)
            if x!=-1:
                return used_elements
            elif x==-1:
                return -1

elemts = [535, 508, 456, 612, 764, 628, 530, 709, 676, 546, 579, 676,
          564, 565, 742, 657, 577, 514, 650, 590, 621, 642, 684, 567, 670, 609, 571, 655, 681, 615, 617, 569, 656, 615,
          542, 711, 777, 763, 663, 657, 532, 630, 636, 445, 495, 567, 603, 598, 629, 651, 608, 653, 669, 603, 655, 622,
          578, 551, 560, 712, 642, 637, 545, 631, 479, 614, 710, 458, 615, 659, 636, 578, 629, 622, 584, 582, 650, 636,
          693, 527, 577, 711, 601, 530, 1028, 683, 589, 590, 670, 409,582, 635, 558, 607, 648, 542, 726, 534, 540, 590, 649, 482, 664, 629, 555, 596, 613, 572, 516, 479, 562, 452,
          586]

max_no_elements = int(input())
wanted_sum = int(input())
solution = -1
while solution == -1:
    solution = find_the_elements(current_sum=0, wanted_sum=range(wanted_sum - 10, wanted_sum + 1), used_elements=[], max_number_of_elements=max_no_elements, n_o_elements=0)
print(solution) 

That's my solution for it but I think I should do it differently because originally I work with a much bigger list and each elements(integer) of the list is much 10-20x bigger.

1 answer

  • answered 2021-02-22 23:18 Alain T.

    Recursion with memoization (i.e. dynamic programing) is probably the best approach for this:

    def closeSum(A,S,N,p=0,memo=None):
        if not N: return [],0
        if memo is None: memo = dict()          # memoization
        if (S,N,p) in memo: return memo[S,N,p]
        best,bestSum = [],0
        for i,a in enumerate(A[p:],p):  # combine remaining elements for sum
            if a>S: continue            # ignore excessive values
            if a == S: return [a],a     # end on perfect match 
            r   = [a] + closeSum(A,S-a,N-1,i+1,memo)[0] # extend sum to get closer
            sr  = sum(r)
            if sr+10>=S and sr>bestSum: # track best so far
                best,bestSum = r,sr 
        memo[S,N,p]=(best,sum(best))    # memoization
        return best,sum(best)
    

    output:

    elemts = [535, 508, 456, 612, 764, 628, 530, 709, 676, 546, 579, 676,
              564, 565, 742, 657, 577, 514, 650, 590, 621, 642, 684, 567, 670, 609, 571, 655, 681, 615, 617, 569, 656, 615,
              542, 711, 777, 763, 663, 657, 532, 630, 636, 445, 495, 567, 603, 598, 629, 651, 608, 653, 669, 603, 655, 622,
              578, 551, 560, 712, 642, 637, 545, 631, 479, 614, 710, 458, 615, 659, 636, 578, 629, 622, 584, 582, 650, 636,
              693, 527, 577, 711, 601, 530, 1028, 683, 589, 590, 670, 409,582, 635, 558, 607, 648, 542, 726, 534, 540, 590, 649, 482, 664, 629, 555, 596, 613, 572, 516, 479, 562, 452,
              586]
    
    closeSum(elemts,1001,3) 
    [456, 545], 1001
    
    closeSum(elemts,5522,7) 
    [764, 742, 777, 763, 712, 1028, 726], 5512
    
    closeSum(elemts,5522,10) 
    [535, 508, 456, 612, 764, 628, 530, 546, 409, 534], 5522
    

    It works relatively fast when there is an exact match but still takes a while for the larger values/item counts when it doesn't.

    Note that there is still room for some optimization such as keeping track of the total of remaining elements (from position p) and exiting if they can't add up to the target sum.