CODEWITHSUNDEEP
pythonlistmathsum
Louie Lee
Louie Lee

Reputation: 283

Use python to solve a math problem: sum up to a value as close as possible

I have a list of numbers. Now if I set a fixed value V, is it possible for python to divide the list into several groups such that each group's sum is not smaller than V (get those groups as many as possible)?

Ex: if the list is [1,2,3,4,5] and the V is 6, then the result should be [[1,5],[2,3,4]]. Dividing the group means you cannot use the same original item more than once.

There's no limitation on how many items each sublist can contain and also the numbers are not in order (can be some random numbers). Could someone help me out? So far my solution is sum up all the combinations and compare the sums. But I'm pretty sure there should be a more effective solution. Thanks!

My solution: I kinda use this first and do the rest job by my mind, so it doesn't worth a further development. 

import itertools
import math

stuff = list(range(10))
v = 6

for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        if math.fsum(subset) > v: 
            print(subset,math.fsum(subset))

Upvotes: 1

Views: 324

Answers (2)

Alexey S. Kiselev
Alexey S. Kiselev

Reputation: 89

My solution has O(n^2) time complexity. You can sort list in ascending order. Then iterate over list from the end. As You want max number of subsets, then each value greater then V added to array. In other case collect values from right and left corners while achieve sum of subset equals to V:

def get_value_in_dict(d):
    return d.get(list(d)[0])

# Implementation for a list of dictionaries like [{'apple':1},{'pear':22},{'hat':23},{'glass':44}]
def sum_up_to_value(stuff, val):
    new_stuff = []
    sorted_stuff = list(sorted(stuff, key=lambda el: get_value_in_dict(el)))
    n = len(stuff)
    pointer_r = n - 1
    pointer_l = 0
    queue = list()

    while pointer_r >= pointer_l:
        if get_value_in_dict(sorted_stuff[pointer_r]) >= val:
            new_stuff.append([sorted_stuff[pointer_r]])
        else:
            subsum = get_value_in_dict(sorted_stuff[pointer_r])
            substuff = []
            while pointer_l < pointer_r and subsum < val:
                # get from queue
                while len(queue) and subsum < val:
                    temp = queue.pop(0)
                    subsum += get_value_in_dict(temp)
                    substuff.append(temp)
                # get from input
                else:
                    if subsum < val:
                        subsum += get_value_in_dict(sorted_stuff[pointer_l])
                        substuff.append(sorted_stuff[pointer_l])
                        pointer_l += 1
            substuff.append(sorted_stuff[pointer_r])
            # returns back smallest elements
            while subsum - get_value_in_dict(substuff[0]) >= val:
                temp = substuff.pop(0)
                queue.append(temp)
                subsum -= get_value_in_dict(substuff[0])

            if subsum < val:
                # add substuff to last element of new_stuff
                temp = new_stuff.pop()
                new_stuff.append(temp + substuff)
            else:
                new_stuff.append(substuff)
        pointer_r -= 1
    return new_stuff  # list(map(lambda el: sorted(el, key=lambda el_d: get_value_in_dict(el_d)), new_stuff)) for sorted by value elements in resulting list

Upvotes: 1

user8408080
user8408080

Reputation: 2468

If you sort your list, this should get you the desired result, although it's not very beautiful as I have to admit:

stuff = range(10)
l = len(stuff)
v = 6

new_stuff = []
i = 0
active = True

while active:
    sub_stuff = []
    subsum = 0
    while subsum<v:
        if i>(l-1):
            active = False
            break
        el = stuff[i]
        sub_stuff.append(el)
        subsum += el
        i += 1
    else:
        new_stuff.append(sub_stuff)

It just goes through your list and sums element until their sum is 6 or higher and then appends a list of those elements to new_stuff and goes on to find the next list.

Try a test list like:

import numpy as np
stuff = sorted(np.random.randint(0,10,100))

Upvotes: 0

Related Questions