Используйте python для решения математической задачи: суммируйте как можно ближе к значению

Question

У меня есть список номеров. Теперь, если я установлю фиксированное значение V, возможно ли для Python разделить список на несколько групп так, чтобы сумма каждой группы была не меньше V (получить эти группы как можно больше)?

Пример: если список равен [1,2,3,4,5], а V равно 6, то результат должен быть [[1,5], [2,3,4]]. Разделение группы означает, что вы не можете использовать один и тот же оригинальный элемент более одного раза.

Нет ограничений на количество элементов, которое может содержать каждый подсписок, а также номера не в порядке (могут быть некоторые случайные числа). Может ли кто-нибудь помочь мне? Пока что мое решение состоит в суммировании всех комбинаций и сравнении сумм. Но я уверен, что должно быть более эффективное решение. Спасибо!

Мое решение: сначала я пользуюсь этим, а остальное делаю мысленно, поэтому дальнейшее развитие не стоит.

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))

Answer 1

Мое решение имеет O (n ^ 2) временную сложность. Вы можете отсортировать список в порядке возрастания. Затем переберите список с конца. Так как Вы хотите максимальное количество подмножеств, то каждое значение больше V добавляется в массив. В другом случае собирайте значения из правого и левого углов, в то время как сумма подмножеств равна 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

Answer 2

Если вы сортируете свой список, это должно дать вам желаемый результат, хотя он не очень красив, как я должен признать:

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)

Он просто проходит через ваш список и суммирует элементы, пока их сумма не станет6 или выше, а затем добавляет список этих элементов к new_stuff и продолжает поиск следующего списка.

Попробуйте список тестов, например:

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