Описание проблемы:
В популярном баре у каждого посетителя есть набор любимых напитков, и он с радостью примет любой напиток из этого набора. Например, в следующей ситуации покупатель 0 будет доволен напитками 0, 1, 3 или 6.
настройки = {
0: [0, 1, 3, 6],
1: [1, 4, 7],
2: [2, 4, 7, 5], < br /> 3: [3, 2, 5],
4: [5, 8]
}
Ленивый бармен, работающий в этом баре, пытается уменьшить свои усилия, ограничив напиток рецепты, которые он должен запомнить. Учитывая ввод словаря, подобный приведенному выше, верните наименьшее количество напитков, которые он должен выучить, чтобы удовлетворить всех клиентов.
Для введенных выше данных ответ будет 2, так как напитки 1 и 5 понравятся всем.
Примеры:
Тип ввода:
аргумент 1:
2D-массив, где каждый номер строки представляет уникального клиента, а значения каждой строки представляют напитки, которые удовлетворяют соответствующего клиента
аргумент 2:
количество напитков
аргумент 3:
количество клиентов.
Тип вывода: Целочисленное значение, представляющее наименьшее количество напитков, которое удовлетворит всех клиентов.
Ввод:
{
{0,1,3,6},
{1,4,7},
{2,4,7 , 5},
{3,2,5},
{5,8}
}
, 9, 5
Вывод : 2
Алгоритм:
a) Создайте 2D-массив с именем ar размером m * (n + 1), где m представляет количество напитков, а n представляет количество клиентов.
b) Каждый индекс строки указывает количество / идентификатор напитков, а каждый индекс столбца указывает номер / идентификатор клиента.
c) Заполните вновь созданный массив значением 1 везде, где есть представляет собой комбинацию напитка и покупателя.
d) Например, как видно из ввода, покупатель 0 удовлетворен напитками 0,1,3,6, поэтому мы устанавливаем значение arr [0] [0], arr [1] [0],
arr [3] [0], arr [6] [0] как 1.
e) Дополнительный столбец, который мы создали в массиве arr и названный sum, используется для хранения количества клиентов, которых удовлетворяет каждый напиток.
f) Например, arr [0] [n + 1] хранит количество клиентов, удовлетворенных напитком 0, которое равно 1. Аналогично arr [1] [n + 1] представляет < br /> количество клиентов, удовлетворенных напитком 1, равное 2.
g) Просмотрите последний столбец массива arr и найдите максимальное значение и соответствующий ему индекс строки.
h) Максимальное значение - 3, а индекс строки - 5.
i) Индекс строки из шага выше представляет номер напитка, который удовлетворяет максимальное количество клиентов.
j) Мы увеличиваем значение переменной count до единицы, так как мы нашли один напиток с номером 5, который может удовлетворить в общей сложности 3 клиента
с именем 2,3 , 4.
k) Вот сложная часть. Нам все еще нужно найти другие напитки, которые могут удовлетворить двух оставшихся клиентов 0 и 1.
l) Итак, мы удаляем строку с индексом 5 и столбцы с индексом 2, 3, 4 в массиве arr. Потому что мы уже учли эти напитки и клиентов.
m) Снова вычислите значения последнего столбца со строками и столбцами, оставшимися после предыдущего шага.
n) Итак, мы повторяем ту же процедуру. от шага g до шага m до тех пор, пока количество пропущенных клиентов не станет равным нулю.
Примечание. Технически для имитации удаления строк и столбцов выполните следующую процедуру.
а) Мы проходим по строке, в которой максимальное количество клиентов с индексом 5. (которое мы нашли на шаге g).
b) Если вы встретите значение 1, приостановите обход строки и начните обход столбца.
c) Например, при обходе строки с индексом 5 значение arr [5] [2] равно 1. Итак, приостановите обход строки и начните перемещение
по столбцу . т.е. от arr [0] [2] до arr [m] [2].
d) Если при просмотре столбца вы найдете значение 1, сделайте его нулевым и уменьшите значение в последний столбец на 1 в той же строке. Например, значения arr [2] [2], arr [4] [2], arr [5] [2], arr [7] [2]] равны 1. Поэтому сделайте их равными 0 и уменьшите значения arr [2] [n + 1], arr [4] [n + 1], arr [5] [n + 1], arr [7] [n + 1] на 1.
e) И, наконец, возобновите перемещение ряда с шага b и следуйте процедуре до конца ряда.
КОД (JAVA):
