Предприятие производит закупку изделий A и B, на которую выделена
Условие
Предприятие производит закупку изделий A и B, на которую выделена определённая сумма денег. У поставщика есть в наличии различные модификации этих изделий по различной цене. При покупке необходимо руководствоваться следующими правилами:1. Нужно купить как можно больше изделий, независимо от их типа и модификации.2. Если можно разными способами купить максимальное количество изделий, нужно выбрать тот способ, при котором будет куплено как можно больше изделий A.3. Если можно разными способами купить максимальное количество изделий с одинаковым количеством изделий A, нужно выбрать тот способ, при котором вся покупка будет дешевле.Определите, сколько всего будет куплено изделий A и какая сумма останется неиспользованной.Входные данные.Задание 26Первая строка входного файла содержит два целых числа: N — общее количество изделий у поставщика и M — сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена изделия в рублях) и символ (латинская буква A или B), определяющий тип изделия. Все данные в строках входного файла отделены одним пробелом.В ответе запишите два целых числа: сначала количество закупленных изделий типа A, затем оставшуюся неиспользованной сумму денег.Пример входного файла:6 13030 B50 B60 A20 A70 A10 BВ данном случае можно купить не более 4 изделий, из них не более 2 изделий A. Минимальная цена такой покупки 120 руб. (покупаем изделия 30B, 60A, 20A, 10B). Останется 10 руб. В ответе надо записать числа 2 и 10. Ответ:
Ответ
157267
Решение по шагам
Как рассуждать
Решение. Создадим два двумерных массива. В первый массив считаем все элементы из файла и отсортируем его по возрастанию. После этого посчитаем максимальное количество изделий, которое можем закупить на заданную сумму, последовательно прибавляя к переменной sum цену изделия в текущем элементе. Далее в отдельный двумерный массив вынесем только оставшиеся изделия A. Далее будем перебирать уже взятые изделия с конца, пытаясь заменить изделия B на изделия A таким образом, чтобы сумма взятых изделий не превышала заданную сумму. После этого посчитаем, сколько изделий A получилось закупить. Приведём решение на языке 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
Осталось ещё 1 шаг — откроются после входа:
- Шаг 2
Бесплатно · займёт минуту