На грузовом судне необходимо перевезти контейнеры, имеющие одинаковый габарит и разные массы (некоторые контейнеры могут иметь одинаковую массу). Общая масса всех контейнеров превышает грузоподъёмность судна. Количество грузовых мест на судне не меньше количества контейнеров, назначенных к перевозке. Какое максимальное количество контейнеров можно перевезти за один рейс и какова масса самого тяжёлого контейнера среди всех контейнеров, которые можно перевезти за один рейс?
Входные данные.
В первой строке входного файла находятся два числа: S — грузоподъёмность судна (натуральное число, не превышающее 100 000) и N — количество контейнеров (натуральное число, не превышающее 20 000). В следующих
Выходные данные.
Два целых неотрицательных числа: максимальное количество контейнеров, которые можно перевезти за один рейс и масса наиболее тяжёлого из них.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно транспортировать за один раз максимум два контейнера. Возможные массы этих двух контейнеров —
Ответ:
Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с оставшейся грузоподъёмностью, получим максимальное количество контейнеров, которые можно перевезти. Далее, вычитая из найденной суммы наибольшую массу контейнера в текущей последовательности, будем пробовать прибавлять контейнеры с большей массой. Если такой контейнер будет найден, то заменяем значение контейнера с наибольшей массой, который возможно поместить на судно.
Приведём решение на языке Pascal.
var
i, j, t: integer;
a: array [1..10000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, s, n);
for i := 1 to n do readln(f, a[i]);
for i := 1 to n do
for j := i + 1 to n do
if a[i] > a[j] then begin
t := a[i];
a[i] := a[j];
a[j] := t;
end;
sum := 0;
maxi := 1;
for i := 1 to n do
if sum + a[i] <= s then begin
sum := sum + a[i];
maxi := i;
end;
t := a[maxi];
for i := maxi to n do
if ((sum - t) + a[i]) <= s then begin
sum := sum - t + a[i];
t := a[i];
end;
writeln(maxi, ' ', t);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ —
Ответ: 1612 90.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open('26 (5).txt')
data = f.readlines()
s = data[0].split()
s = int(s[0])
del (data[0]) # первая строка больше не нужна, удаляем ее
for i in range(0, len(data)):
data[i] = int(data[i])
data = sorted(data)
summa = 0
for count in range(0, len(data)):
if summa + data[count] > s: break
summa += data[count]
print(count)
zapas = s - summa
for i in range(0, len(data)):
if data[i] - data[count - 1] <= zapas:
itog = data[i]
print(itog)
Приведём решение Максима Митина (Нижний Новгород) на языке Python.
f = open('26.txt')
l = f.readline()
limit = int(l.split()[0])
n = int(l.split()[1])
a = [int(x) for x in f.readlines()]
a.sort()
ns = 0
k = 0
for i in a:
if ns + i <= limit:
ns += i
k += 1
temp = i
else:
ns -= temp
for j in a:
if ns + j <= limit:
temp = j
else:
break
break
print(k, temp)
Приведём решение Ильи Крылова на языке Python.
s = [i for i in open('26.txt').readlines()]
capacity = int(s[0].split()[0])
containers = [int(i) for i in s[1:]]
selectedContainers = []
containers = sorted(containers)
while (capacity - sum(selectedContainers)) >= containers[0]:
selectedContainers.append(containers[0])
containers.pop(0)
# Получили массив с максимальным количеством самых легких контейнеров
# Теперь нужно определить какой максимальный контейнер может поместиться в последний слот
maxLastContainerCapacity = capacity - sum(selectedContainers[:-1])
biggestContainer = max([container for container in containers if container <= maxLastContainerCapacity])
print(len(selectedContainers), biggestContainer)
Приведём решение Юрия Красильникова на языке Python.
f = open('26.txt')
s,n = list(map(int,f.readline().split()))
a = sorted([int(x) for x in f])
k = 0
for x in a:
if x > s: break
s -= x
last = x
k += 1
s += last
m = max([x for x in a if x <= s])
print(k,m)