Разделите список Python на подмножества списков (чем меньше число подмножеств, тем лучше), каждый с суммой меньше, чем K

Question

Я довольно новичок в питоне. Я делаю программу и столкнулся с проблемой, которую можно описать следующим образом:

Допустим, у нас есть список чисел (каждое меньше 5) [1.5, 3, 4, 2.5 , 1, 4, 0.5 etc]. Я хочу разделить этот список на подмножества списка с условием, что сумма элементов в каждом подмножестве равна <= 5. Список может содержать до 200 элементов.

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

Answer 1

Это называется проблемой упаковки бункера . Это хорошо изученная NP-полная проблема, означающая, что ни один из известных алгоритмов не дает точных ответов (т. Е. С истинным минимальным числом подсписков), а также эффективно работает для больших входных данных.

Однако, поскольку вам требуется только«хорошее» достаточно решение, вам повезло;Есть много хороших эвристик , которые дают довольно хорошие ответы на практике. Хорошим простым алгоритмом является «Уменьшение по первому размеру»:

1. Сортировка элементов по убыванию (т. Е. По убыванию).
2. Инициализация списка для хранения подсписков. Первоначально, их нет.
3. Для каждого элемента:
   • Если есть какие-либо подсписки с достаточным количеством свободного места, вставьте элемент в первый.
   • В противном случае создайте новыйпустой подсписок и вставьте туда элемент.

Получается, что решения всегда дают не более (11/9) b + 1 подсписков, где b - количествоподсписки, используемые оптимальным решением ( Yue, 1990 ).

Answer 2

Я бы поспорил, что это скорее проблема алгоритма, чем специфичная для python, но один алгоритм, который приходит мне в голову и который кажется достаточно простым, состоит в сортировке списка и создании «сегментов» (подсписков). ), которые начинаются с элемента max и добавляются с начала списка до тех пор, пока его нельзя будет добавить.

В Python это может выглядеть примерно как список

x = [1.5, 3, 4, 2.5 , 1, 4, 0.5]
x.sort()
buckets = []

while True:
    # if the list is empty, break
    if x == []:
        break

    last_elem = x.pop()  # pop removes the last element and returns it
    new_bucket = [last_elem]  # create a new bucket initially with just that
    new_bucket_sum = last_elem

    # for the remaining numbers
    num_added = 0
    for num in x:
        if num + new_bucket_sum > 5:
            break
        new_bucket.append(num) # add it to the sub-list
        new_bucket_sum += num  # account for the sum
        num_added += 1  # increase our count for this iteration

    buckets.append(new_bucket)  # add the bucket
    x = x[num_added:]  # take a sub-list of x (getting rid of the numbers added)


    # Note that we now recurse until all numbers have been placed in to buckets

# After this for loop breaks, you have all the buckets
print(buckets)

Это был мойинстинкт. Я бы сказал, что для написания этого алгоритма есть более «питонические» способы, но так как вы новичок в Python, я подумал, что было бы полезно разбить его и прокомментировать. Там также могут быть лучшие алгоритмы там. Приветствия

Answer 3

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

import numpy as np


#base_randlist = np.random.random(200) * 5

base_randlist = np.array([1.5, 3, 4, 2.5 , 1, 4, 0.5])

print(base_randlist)

sets = []
for i in range(10000):

    set_ = []
    subset = []
    randlist = base_randlist

    while randlist.shape[0] != 0:
        while True:
            if randlist.shape[0] == 0:
                set_.append(subset)
                break
            ind = np.random.randint(0, randlist.shape[0])
            last_subset = subset.copy()
            subset.append(randlist[ind])

            if sum(subset) <= 5:
                randlist = np.delete(randlist, ind)
            else:
                set_.append(last_subset)
                subset = []
                break
    sets.append(set_)

min_setnum = np.inf
for i, s in enumerate(sets):
    if min_setnum > len(s):
        min_setnum = len(s)
        min_ind = i

print(sets[min_ind])
print(min_setnum)

Out:

[1.5 3.  4.  2.5 1.  4.  0.5]
[[3.0, 0.5], [1.5, 2.5], [4.0], [4.0, 1.0]]
4

Answer 4

Просто подумал добавить, что если элементы результирующих списков списков ДОЛЖНЫ поддерживать свой первоначальный порядок (относительно списка ввода), то вы можете сделать это:

elts = [1.5, 3, 4, 2.5 , 1, 4, 0.5]
res = []

temp = []      # for accumulating the numbers
temp_sum = 0   # the sum of the accumulated numbers

for e in elts:
    temp_sum += e    # update the sum with current element
    if temp_sum > 5:
        # if updating the sum with the current element
        # makes the sum overshoot the limit
        # then don't accumulate the current element
        # instead ...
        res.append(temp)  # append the previously accumulated elements to the result
        temp = [e]        # start a new accumulator with the current element
        temp_sum = e      # start a new accumulated sum with the current element
    else:
        # if updating the sum with the current element
        # does not make the sum overshoot the limit ...
        temp.append(e)    # accumulate current element

# finally, append the last seen accumulator to the result
res.append(temp)

Результат, res, будет [[1.5, 3], [4], [2.5, 1], [4, 0.5]]