Сколько коробок понадобится, чтобы вместить все вещи
Задача вместить некоторое количество вещей в коробки. В одну коробку можно вместить не более 2 вещей. Вещи заданы списком из чисел, обозначающих их вес. Максимальный вес, который можно положить в коробку задан вторым параметром. То есть, если дано ([5, 1, 4, 2, 3], 6), то нам нужно 3 коробки, чтобы вместить все вещи, максимум по 6 кило в коробку (например вот так 1: 5+1, 2: 4+2, 3: 3). Решение у меня есть такое. Но как решить с помощью O(NlogN)?
def count(t,x):
newT = sorted(t[:])
counter = 0
while len(newT) > 0:
i = 0
weight = x - newT[i]
sec = max((i for i in newT if i <= weight), default=0)
newT.remove(newT[i])
if sec in newT: newT.remove(sec)
counter += 1
return counter
if __name__ == "__main__":
print(count([7, 10, 6, 7, 8], 11)) #5
print(count([5, 1, 4, 2, 3], 6)) #3
print(count([1, 3, 5, 999999999, 10000000000, 1000000000], 10000000000)) #4
print(count([1, 2, 3, 4, 5], 5)) #3
Ответы (2 шт):
Есть такая фраза - "Не знаешь как решить задачу - отсортируй данные"
Отсортировали по убыванию. O(nlogn)
Один индекс идёт слева, второй справа.
Для каждого большого веса (индекс слева) находим максимальный, который можно добавить (правый индекс идёт влево), если он есть, и делаем пару. O(n)
В общем, получилось у меня вот такое решение в итоге
def countBoxes(items,weight):
items.sort(reverse=True)
n = len(items)
boxCounter = 0
small = n-1
big = 0
while big <= small:
boxCounter+=1
if weight - items[big] >= items[small]:
small -= 1
big += 1
return boxCounter