Question

Логистическая компания использует контейнеры с максимальной вместимостью *M* кг. Для отправки *N* грузов контейнеры заполняют грузами в порядке убывания веса, пока общая масса грузов не превысит максимальную вместимость *M*. Затем процедуру повторяют для следующего контейнера, пока все грузы не будут размещены. Необходимо определить количество контейнеров для отправки всех грузов и общую загрузку предпоследнего контейнера.**Входные данные**Задание 26

Входные данные представлены в файле следующим образом. В первой строке записаны два числа — количество грузов *N* и максимальная вместимость контейнера *M*. В каждой из следующих *N* строк записано по одному натуральному числу, обозначающему вес груза.**Пример входного файла** 6 100301040501020 В первый контейнер будут помещены грузы весом 50, 40 и 10 кг (общий вес 100 кг), во второй контейнер — грузы весом 30, 20 и 10 кг (общий вес 60 кг). Ответ: 2100.

Ответ:

Accepted Answer

Answer

### СТАТЕМЕНТ

Логистическая компания использует контейнеры с максимальной вместимостью $M$ кг. Для отправки $N$ грузов контейнеры заполняют грузами в порядке убывания веса, пока общая масса грузов не превысит максимальную вместимость $M$. Затем процедуру повторяют для следующего контейнера, пока все грузы не будут размещены. Необходимо определить количество контейнеров для отправки всех грузов и общую загрузку предпоследнего контейнера.

**Входные данные**

В первой строке записаны два числа — количество грузов $N$ и максимальная вместимость контейнера $M$. В каждой из следующих $N$ строк записано по одному натуральному числу, обозначающему вес груза.

**Пример входного файла**

```
6 100
30
10
40
50
10
20
```

В первый контейнер будут помещены грузы весом 50, 40 и 10 кг (общий вес 100 кг), во второй контейнер — грузы весом 30, 20 и 10 кг (общий вес 60 кг). Ответ: 2 100.

### РЕШЕНИЕ

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

Алгоритм:
1. Прочитать количество грузов и вместимость контейнера.
2. Отсортировать веса грузов в порядке убывания.
3. Для каждого контейнера: начиная с самого тяжёлого оставшегося груза, добавлять грузы, пока их сумма не превысит $M$.
4. Повторять до тех пор, пока все грузы не будут размещены.
5. Вывести количество контейнеров и сумму весов в предпоследнем контейнере.

```python
f = open("26_81492.txt")
n, m = map(int, f.readline().split())
boxes = sorted([int(line) for line in f], reverse=True)

containers = []
while boxes:
    current_weight = 0
    current_container = []
    
    i = 0
    while i < len(boxes):
        if current_weight + boxes[i] <= m:
            current_weight += boxes[i]
            current_container.append(boxes[i])
            boxes.pop(i)
        else:
            i += 1
    
    containers.append(current_weight)

print(len(containers), containers[-2])
```

Сложность: $O(n^2)$ в худшем случае (для каждого контейнера может потребоваться проход по оставшимся грузам).

### ОТВЕТ

Задание №26ПрограммированиеЕГЭ по информатике