Нахождение кратчайшего подсписка с суммой больше 50

Question

У меня есть список, и я хочу найти кратчайший подсписок с суммой больше 50. Например, мой список

[8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1]

и я хочу найти кратчайший подсписок, чтобы его сумма превышала 50.

Вывод должен быть как [12.9 , 13.7 , 11.2 , 11.3, 10.4]

Answer 1

это плохое решение (с точки зрения не полного поиска графика и поиска оптимальных значений), но решение правильное

lis =[8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1] 


from collections import defaultdict
dic = defaultdict(list)

for i in range(len(lis)):
    dic[lis[i]]+=[i]

tmp_lis = lis.copy()
tmp_lis.sort(reverse=True)

res =[]
for  i in tmp_lis:
    if sum(res)>50 :
        break
    else:
        res.append(i)

res1 = [(i,dic[i]) for i in res]

res1.sort(key=lambda x:x[1])
solution =[i[0] for i in res1]

выход

[12.9, 13.7, 11.2, 11.3, 10.4]

Answer 2

O (n) решение для списка положительных чисел

Если ваш список не может содержать отрицательные числа , тогда существует линейное решение с использованием обхода двумя указателями.

Отслеживание суммы между обоими указателями. Увеличивайте правый указатель всякий раз, когда сумма меньше 50, и увеличивайте левый в противном случае.

Это обеспечивает последовательность указателей, в пределах которых вы найдете те с минимальным расстоянием. Достаточно использовать min, чтобы получить наименьший интервал из них.

Из-за поведения min это вернет крайний левый подсписок с минимальной длиной, если существует более одного решения.

код

def intervals_generator(lst, bound):
    i, j = 0, 0
    sum_ = 0
    while True:
        try:
            if sum_ <= bound:
                sum_ += lst[j]
                j += 1
            else:
                yield i, j
                sum_ -= lst[i]
                i += 1
        except IndexError:
            break

def smallest_sub_list(lst, bound):
    i, j = min(intervals_generator(lst, bound), key=lambda x: x[1] - x[0])
    return lst[i:j]

Примеры

lst = [8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1]
print(smallest_sub_list(lst, 50)) # [8.4, 10.3, 12.9, 8.2, 13.7]

lst = [0, 10, 45, 55]
print(smallest_sub_list(lst, 50)) # [55]

Решение для общего списка номеров

Если список может содержать отрицательные числа, то вышеприведенное не будет работать , и я считаю, что не существует более эффективного решения, чем перебирать все возможные подсписки.

Answer 3

Если вы ищете любой кратчайший подсписок, это может быть решением (может быть, оптимизировано):

lst = [8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 , 10.4 , 4.2 , 3.3 , 4.0 , 2.1]

def find_sub(lst, limit=50):
    for l in range(1, len(lst)+1):
        for i in range(len(lst)-l+1):
            sub = lst[i:i+l]
            if sum(sub) > limit:
                return sub

>>> print(find_sub(lst))

Вывод:

[8.4, 10.3, 12.9, 8.2, 13.7]

Answer 4

Сортируйте его в порядке убывания и суммируйте первые элементы, пока не наберете + 50,0.

myList = [8.4 , 10.3 , 12.9 , 8.2 , 13.7 , 11.2 , 11.3 ,10.4 , 4.2 , 3.3 , 4.0 , 2.1]

mySublist = []
for i in sorted(myList, reverse=True):
    mySublist.append(i)
    if sum(mySublist) > 50.0:
        break

print mySublist  # [13.7, 12.9, 11.3, 11.2, 10.4]

Учитывая, что вы хотите, это наименьший по размеру подсписок, а не наименьшее по сумме значение.