Для перевозки партии грузов различной массы выделен грузовик, но его грузоподъёмность ограничена, поэтому перевезти сразу все грузы не удастся. Грузы массой
Входные данные.
Первая строка входного файла содержит два целых числа: N — общее количество грузов и M — грузоподъёмность грузовика в кг. Каждая из следующих
В ответе запишите два целых числа: сначала максимально возможное количество грузов, затем их общую массу.
Пример входного файла:
6 605
140
205
120
160
100
340 В данном случае сначала нужно взять груз массой 205 кг. После этого можно вывезти ещё максимум
Ответ:
Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с размером грузоподъемности грузовика, получим максимальное количество грузов, которые могут поместиться в грузовике. Далее, вычитая из найденной суммы вес наибольшего груза в текущей последовательности, будем пробовать прибавлять грузы с большим весом. Далее такую же последовательность действий применим ко второму по величине грузу, потом к третьему и так далее.
Приведём решение на языке PascalABC.
var
i, j, t, count: integer;
a: array [1..1000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n, s);
sum := 0;
count := 0;
for i := 1 to 1000 do a[i] := 0;
for i := 1 to n do begin
readln(f, t);
if ((t >= 200) and (t <= 210) and (sum + t <= s)) then begin
sum := sum + t;
count := count + 1;
end
else
a[i] := t;
end;
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;
maxi := 1;
for i := count+1 to n do
if sum + a[i] <= s then begin
sum := sum + a[i];
count := count + 1;
maxi := i;
end;
writeln(a);
writeln(n);
writeln(maxi);
writeln(sum);
for i := maxi downto 1 do begin
sum := sum - a[i];
t := i;
for j := maxi to n do
if (sum + a[j]) <= s then t := j
else break;
sum := sum + a[t];
n:=t - 1;
maxi := maxi - 1;
end;
writeln(count, ' ', sum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 123 10000.
Ответ: 123 10000.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open('26 (13).txt')
a, b = f.readline().split()
d = []
s = 0
count = 0
for i in f:
if 200 <= int(i) <= 210:
s += int(i)
count += 1
else:
d.append(int(i))
d.sort()
d2 = []
i = 0
while sum(d2) + d[i] <= int(b) - s:
count += 1
d2.append(d[i])
i += 1
k = len(d) - 1
while i > 0:
while k >= 0:
if sum(d2) - d2[i-1] + d[k] <= int(b) - s and d[k] != 0:
d2[i-1] = d[k]
d[k] = 0
i -= 1
break
else:
k -= 1
s += sum(d2)
print(count, s)
Приведём решение Юрия Красильникова на языке Python.
f = open('26.txt')
n,m = list(map(int,f.readline().split()))
g0 = [int(s) for s in f] # все грузы
g = [x for x in g0 if not (200 <= x <= 210)] # грузы кроме диапазона 200 кг - 210 кг
mass = sum(g0) - sum(g) # масса грузов диапазона 200 кг - 210 кг
k = len(g0) - len(g) # количество грузов диапазона 200 кг - 210 кг
g.sort()
kuzov = [] # грузы, которые перевозим
while mass + sum(kuzov) + g[0] <= m: kuzov.append(g.pop(0)) # начальный вариант
for i in range(len(kuzov)-1,-1,-1): # поочередная замена грузов на более тяжелые
limit=m - mass - sum(kuzov) + kuzov[i] # лимит массы
gruz = [x for x in g if x <= limit] # грузы для замены
if not gruz: break # грузов на замену нет
gr = max(gruz) # самый тяжелый груз для замены
g.append(kuzov[i]) # возвращаем груз из кузова
kuzov[i] = gr # заменяем более тяжелым
g.remove(gr) # удаляем взятый груз
print(k + len(kuzov),mass + sum(kuzov))