26.03 Перевоз грузов

Решение 1 ( Excel / LibreOffice):
Сначала откроем текстовый документ, скопируем значения и перенесем их в Excel или LibreOffice. Для удобства числовые значения количества грузов и грузоподъёмность грузовика (, ) подвинем правее в ячейки и . Сортируем данные столбца ( Сортировка и фильтр — Сортировка по возрастанию). Находим первый груз размером и начинаем набирать, пока не получим в правом нижнем углу максимальную сумму, не превышающую . Мы собрали груз массой . У нас остается кг () свободного места. Используем жадный алгоритм: чтобы вывезти максимальное количество грузов, необходимо брать грузы с наименьшей массой до тех пор, пока их суммарная масса меньше грузоподъемности. Поэтому переходим в самый верх и начинаем набирать максимальную массу, не превышающую . Выходит, что мы можем взять груза массой кг. Заменяем груз весом на груз весом , так как займем больше места. Выходит, что мы заняли всё место, значит, сумма равна , а количество .

Решение 2 (Python):

file = open("Задание_26__i0ia.txt")
lines = file.readlines()

n, m = map(int, lines[0].split())
array = list(map(int, lines[1:]))
array = sorted(array)

i = 0
current_sum = 0
last_elem = 0
ind_last = 0
count = 0

while array[i] <= 320:
    if array[i] >= 310 and current_sum + array[i] <= m:
        current_sum += array[i]
        last_elem = array[i]
        count += 1
    else:
        ind_last = i
    i += 1

for j in range(ind_last):
    if current_sum + array[j] <= m:
        current_sum += array[j]
        last_elem = array[j]
        count += 1

for j in range(i, len(array)):
    if current_sum + array[j] <= m:
        current_sum += array[j]
        last_elem = array[j]
        count += 1

free_space = m - current_sum + last_elem

for i in range(len(array) - 1, 0, -1):
    if array[i] <= free_space:
                                                                                                     
                                                                                                     
        current_sum += array[i] - last_elem
        break

print(count, current_sum)