Предприятие производит закупку
1. Нужно купить как можно больше изделий, независимо от их типа и модификации.
2. Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше
3. Если можно разными способами купить максимальное количество изделий с одинаковым количеством
Определите, сколько всего будет куплено
Входные данные.
Первая строка входного файла содержит два целых числа: N — общее количество изделий у поставщика и M — сумма выделенных на закупку денег (в рублях). Каждая из следующих
В ответе запишите два целых числа: сначала количество закупленных изделий
Пример входного файла:
6 130
30 A
50 A
60 B
20 B
70 B
10 A
В данном случае можно купить не более
Ответ:
Создадим два двумерных массива. В первый массив считаем все элементы из файла и отсортируем его по возрастанию. После этого посчитаем максимальное количество изделий, которое можем закупить на заданную сумму, последовательно прибавляя
Приведём решение на языке Pascal.
var
n, m, x, t1, t2, countB, count, i, j: integer;
z: string;
arrayAB: array [1..916, 1..2] of integer;
arrayB: array [1..916, 1..2] of integer;
sum: integer;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n, m);
countB := 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] = 1 then begin
arrayB[x, 1] := arrayAB[i, 1];
arrayB[x, 2] := arrayAB[i, 2];
x := x + 1;
end;
x := 1;
for i := count downto 1 do begin
if arrayAB[i, 2] = 0 then begin
if ((sum - arrayAB[i, 1] + arrayB[x, 1]) > m) then break;
sum := sum - arrayAB[i, 1] + arrayB[x, 1];
arrayAB[i, 1] := arrayB[x, 1];
arrayAB[i, 2] := arrayB[x, 2];
x := x + 1;
end;
end;
for i := 1 to count do
if arrayAB[i, 2] = 1 then countB := countB + 1;
writeln(countB, ' ', m - sum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 154 87.
Ответ: 154 87.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open('26 (11).txt')
n, m = f.readline().split()
arrayAB = [[0] * 2 for i in range(916)]
arrayB = [[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 == 'B':
arrayAB[i][1] = 0
if z == 'A':
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:
arrayB[x][0] = arrayAB[i][0]
arrayB[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] + arrayB[x][0]) > m:
break
sumi = sumi - arrayAB[i][0] + arrayB[x][0]
arrayAB[i][0] = arrayB[x][0]
arrayAB[i][1] = arrayB[x][1]
x += 1
countB = 0
for i in range(count):
if arrayAB[i][1] == 0:
countB = countB + 1
print(countB, m - sumi)
Приведём решение Александра Кузнецова на языке Python.
f = open('26.txt')
n, m = [int(i) for i in (f.readline()).split()]
lA, lB= [], []
l=[]
for i in f:
p, t = [str(j) for j in i.split()]
p=int(p)
l.extend([(p, t)])
f.close()
sumi=0
l.sort()
k=0
for p, t in l:
if sumi+p <= m:
if t=='A': lA.append(p)
if t=='B': k+=1
sumi+=p
elif t=='B' and sumi+p>m and len(lB)<=len(lA):
lB.append(p)
lA.sort()
lA=lA[::-1]
lB.sort()
for i in lB:
for j in range(len(lA)):
if sumi-lA[j]+i<=m:
sumi=sumi-lA[j]+i
k+=1
lA.pop(j)
break
print(k, m-sumi)