Логистическая компания использует контейнеры с максимальной вместимостью M кг. Для отправки N грузов контейнеры заполняют грузами в порядке убывания веса, пока общая масса грузов не превысит максимальную вместимость M. Затем процедуру повторяют для следующего контейнера, пока все грузы не будут размещены. Необходимо определить количество контейнеров для отправки всех грузов и общую загрузку предпоследнего контейнера.
Входные данные
Входные данные представлены в файле следующим образом. В первой строке записаны два числа — количество грузов N и максимальная вместимость контейнера M. В каждой из следующих N строк записано по одному натуральному числу, обозначающему вес груза.
Пример входного файла
6 100
30
10
40
50
10
20 В первый контейнер будут помещены грузы весом 50, 40 и 10 кг (общий вес 100 кг), во второй контейнер — грузы весом 30, 20 и 10 кг (общий вес 60 кг). Ответ: 2100.
Ответ:
Приведём решение на языке Python.
f = open("26_81492.txt")
n, m = map(int, f.readline().split())
boxes = sorted([int(i) for i in f], reverse=True)
count = 0
otv = []
while len(boxes):
count += 1
temp_b = []
temp_w = 0
for box in boxes[:]:
if temp_w + box <= m:
temp_w += box
temp_b.append(box)
boxes.remove(box)
otv.append(temp_b)
print(count, sum(otv[-2]))
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 4955 995.
Ответ: 4955 995.
Приведём решение Юрия Красильникова на языке Python.
f=open('26_81492.txt')
n,m=map(int,f.readline().split())
a=sorted([int(s) for s in f])
cont=[]
while a:
c=a.pop()
i=len(a)-1
while i >= 0:
if c+a[i] <= m: c+=a.pop(i)
i-=1
cont.append(c)
print(len(cont),cont[-2])