Предприятие производит закупку
1. Нужно купить как можно больше изделий, независимо от их типа и модификации.
2. Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше
3. Если можно разными способами купить максимальное количество изделий с одинаковым количеством
Определите, сколько всего будет куплено
Входные данные.
Первая строка входного файла содержит два целых числа: N — общее количество изделий у поставщика и M — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и символ (латинская
В ответе запишите два целых числа: сначала количество закупленных изделий
Пример входного файла:
6 130
30 B
50 B
60 A
20 A
70 A
10 B
В данном случае можно купить не более
Ответ:
Создадим два двумерных массива. В первый массив считаем все элементы из файла и отсортируем его по возрастанию. После этого посчитаем максимальное количество изделий, которое можем закупить на заданную сумму, последовательно прибавляя
Приведём решение на языке Pascal.
var
n, m, x, t1, t2, countA, count, i, j: integer;
z: string;
arrayAB: array [1..916, 1..2] of integer;
arrayA: array [1..916, 1..2] of integer;
sum: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n, m);
countA := 0;
count := 0;
sum := 0;
for i := 1 to n do begin
if not eof(f) then
readln(f, x, z)
else break;
if z.Contains('A') then begin
arrayAB[i, 1] := x;
arrayAB[i, 2] := 0;
end;
if z.Contains('B') then begin
arrayAB[i, 1] := x;
arrayAB[i, 2] := 1;
end;
end;
for i := 1 to n-1 do
for j := i + 1 to n do
if arrayAB[i, 1] > arrayAB[j, 1] then begin
t1 := arrayAB[i, 1];
t2 := arrayAB[i, 2];
arrayAB[i, 1] := arrayAB[j, 1];
arrayAB[i, 2] := arrayAB[j, 2];
arrayAB[j, 1] := t1;
arrayAB[j, 2] := t2;
end;
for i := 1 to n do
if (sum + arrayAB[i, 1]) < m then begin
sum := sum + arrayAB[i, 1];
count := count + 1;
end
else break;
x := 1;
for i := count + 1 to n do
if arrayAB[i, 2] = 0 then begin
arrayA[x, 1] := arrayAB[i, 1];
arrayA[x, 2] := arrayAB[i, 2];
x := x + 1;
end;
x := 1;
for i := count downto 1 do begin
if arrayAB[i, 2] = 1 then begin
if ((sum - arrayAB[i, 1] + arrayA[x, 1]) > m) then break;
sum := sum - arrayAB[i, 1] + arrayA[x, 1];
arrayAB[i, 1] := arrayA[x, 1];
arrayAB[i, 2] := arrayA[x, 2];
x := x + 1;
end;
end;
for i := 1 to count do
if arrayAB[i, 2] = 0 then countA := countA + 1;
writeln(countA, ' ', m - sum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 157 267.
Ответ: 157 267.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open('26.txt')
n, m = f.readline().split()
arrayAB = [[0] * 2 for i in range(916)]
arrayA = [[0] * 2 for i in range(916)]
n = int(n)
m = int(m)
count = 0
sumi = 0
for i in range(n):
x, z = f.readline().split()
arrayAB[i][0] = int(x)
if z == 'A':
arrayAB[i][1] = 0
if z == 'B':
arrayAB[i][1] = 1
arrayAB.sort()
i = 0
while m > arrayAB[i][0] + sumi:
if (sumi + arrayAB[i][0]) < m:
sumi = sumi + arrayAB[i][0]
count += 1
i += 1
x = 1
for i in range(count, n):
if arrayAB[i][1] == 0:
arrayA[x][0] = arrayAB[i][0]
arrayA[x][1] = arrayAB[i][1]
x += 1
x = 1
for i in range(count - 1, -1, -1):
if arrayAB[i][1] == 1:
if (sumi - arrayAB[i][0] + arrayA[x][0]) > m:
break
sumi = sumi - arrayAB[i][0] + arrayA[x][0]
arrayAB[i][0] = arrayA[x][0]
arrayAB[i][1] = arrayA[x][1]
x += 1
countA = 0
for i in range(count):
if arrayAB[i][1] == 0:
countA = countA + 1
print(countA, m - sumi)
Приведём решение Ильи Пащука (Липецк) на языке Python.
f = open('26.txt') # считывание входных данных
maxsum = int(f.readline().replace('\n','').split(' ')[1])
l = f.readlines()
f.close()
ll = []
for i in l:
ii = i.replace('\n','').split(' ')
ii[0] = int(ii[0])
ll.append(ii)
# создаём отдельные массивы для изделий a и b, и сортируем все 3 массива
alist = [k[0] for k in ll if k[1] == 'A']
blist = [k[0] for k in ll if k[1] == 'B']
alist.sort()
blist.sort()
ll.sort(key=lambda k: k[0])
# считаем максимальное количество изделий
msum = 0
maxc = 0
for i in ll:
if msum + i[0] <= maxsum:
msum += i[0]
maxc += 1
else: break
# "закупаем" максимальное количество изделий A
ba = []
for i in alist:
if len(ba) >= maxc: break
if sum(ba) + i <= maxsum:
ba.append(i)
else: break
# докупаем изделия B, при необходимости удаляя изделия A, пока не доберём до максимального значения
bb = []
for i in blist:
if len(ba) + len(bb) >= maxc: break
if sum(ba) + sum(bb) + i <= maxsum:
bb.append(i)
else:
while sum(ba) + sum(bb) + i > maxsum: del ba[-1]
bb.append(i)
# вывод ответа
print(len(ba))
print(maxsum - (sum(ba) + sum(bb)))
Приведём решение Вячеслава Ладынского на языке Python.
f = open('26.txt')
n, m = map(int, f.readline().split())
f = [i.split() for i in f]
f = sorted([[int(i[0]), i[1]] for i in f])
a = []
b = []
for i in range(len(f)):
if sum(a+b) + f[i][0] <= m:
if f[i][1] == 'A':
a.append(f[i][0])
f[i] = []
elif f[i][1] == 'B':
b.append(f[i][0])
f[i] = []
f = [i for i in f if i != []]
for i in f:
if i[1] == 'A':
if sum(a+b) - b[-1] + i[0] <= m:
a.append(i[0])
b.pop(-1)
print(len(a), m - sum(a + b))
Приведём решение Юрия Красильникова на языке Python.
f=open('26.txt')
n,s=map(int, f.readline().split())
a=sorted([[int(s.split()[0]),s.split()[1]] for s in f],key=lambda x: x[0],reverse=True)
packa,packb=[],[]
while s >= a[-1][0]:
x=a.pop()
(packa if x[1]=='A' else packb).append(x)
s-=x[0]
aa=[x for x in a if x[1]=='A']
while aa and packb and aa[-1][0]-packb[-1][0] <= s:
s-=aa[-1][0]-packb[-1][0]
packb.pop()
packa.append(aa.pop())
print(len(packa),s)