Отправлено: 23.02.23 10:33. Заголовок: №6017

''' (№ 6017) (А. Богданов) Транспортная компания владеет автомобилями с грузоподъемность M. Для транспортировки N грузов автомобили загружают предметами
по убыванию веса, пока общая масса предметов не превышает грузоподъемность M. И далее процедуру повторяют для другого грузовика, до тех пор, пока все предметы
не будут погружены. Нужно определить количество автомобилей для транспортировки всех предметов и общую загрузку предпоследнего автомобиля.
Входные данные представлены в файле 26-99.txt следующим образом. . В первой строке записаны два числа – количество грузов N и грузоподъёмность автомобиля M. В
каждой из следующих N строк записано по одному натуральному числу, обозначающему вес груза.
Пример входного файла::
6 100
30
10
40
50
10
20
В первый автомобиль будут погружены грузы весом 50, 40 и 10, во второй – грузы весом 30, 20 и 10. Ответ: 2 100.
Спрятать ответ

38 1481'''

Не сходятся ответы, посмотрел работу программы глазками, вроде правильно работает, помогите найти ошибку. Загрузка автомобиля с суммой 1481 есть в массиве, но она не предпоследний.

 
 f = open('26-99.txt') 
 n, m = map(int, f.readline().split()) 
 s = sorted([int(x) for x in f.readlines()], reverse=1) 
 ms = [] 
 mx = [] 
 while len(s) > 0: 
     ms = [s[0]] 
     s.pop(s.index(s[0])) 
     while len([x for x in s if x < m - sum(ms)])>0: 
         a = [x for x in s if x < m - sum(ms)][0] 
         ms.append(a) 
         s.pop(s.index(a)) 
     mx.append(ms) 
 print(len(mx), sum(mx[-1]))

 Отправлено: 23.02.23 13:27. Заголовок: Задача однопроходная..

Задача однопроходная. А у вас в коде сложность O(N^3) три вложенных цикла и куча списков. Достаточно только списка s.
Удалите все лишнее и сделайте на целочисленных переменных. Больше кода, проще запутаться.

 Отправлено: 24.02.23 09:54. Заголовок: Нашёл ошибку

Если кому-то было интересно, то я поставил неправильное условие в генераторе:

 
 [x for x in s if x < m - sum(ms)] 
 

не "меньше", а "меньше или равно должно быть"