Оптимальное решение - теория программирования

Question

Я хотел бы, чтобы кто-то объяснял разные подходы к простой проблеме, а затем я попытаюсь реализовать ее в PHP для более широкого применения.

У меня есть пять человек, которые выбирают, кто получает комнату, в которой есть пять комнат: Большой, Большой, Средний, Средний и Маленький.

Person 1 orders the rooms Grand, Large 
Person 2 orders the rooms Large, Medium 
Person 3 orders the rooms Large, Small 
Person 4 orders the room Medium 
Person 5 orders the rooms Large, Medium 

Где недостающий номер один они не заинтересованы.

Какой справедливый способ выбрать, кто получает каждую комнату?

Answer 1

Справедливость не всегда четко определена.

Однако в этом случае кажется, что человек может либо получить комнату, которую он просит, либо нет. Таким образом, можно утверждать, что все решения, в которых одинаковое количество людей получают комнату, которую они хотят, одинаково справедливы, а решения, в которых больше людей получают комнату, которую они хотят, более справедливы, чем те, где меньше получают то, что они хотят (мы таким образом, не давая предпочтения одного человека).

В вашем примере есть только одно решение, где каждый получает комнату, которую он хочет. Таким образом, это «самое справедливое» решение.

Алгоритм поиска этого - это просто поиск по глубине (или, если нужно ускорение), который учитывает все возможные распределения и находит максимальный.

Answer 2

Используйте эвристику, чтобы вычислить соответствующее значение каждой ситуации. Например. если человек остается без комнаты, значение будет низким или отрицательным. Если каждый человек останется с самой большой комнатой, которую они заказали, значение будет самым высоким.

Вычислить это значение для каждой ситуации, а затем принять ситуацию с наивысшим значением.