Алгоритм оптимального «пересечения» двух результатов?

Question

У меня есть два результата, и я хотел бы получить лучший "порядок" обоих.Пример:

У нас есть гонка с 5 людьми в одной гонке и 7 в другой.Итог: раса 1.

1. Karl
2. Fred
3. John
4. Peter
5. Sid

раса 2.

1. Steven
2. John
3. Karl
4. Peter
5. Aron
6. Fred
7. Kevin

Задание таково: что входит в топ-7 обеих этих рас?то, что номер 1 в данном случае - Карл, поскольку он занимает 1-е место и 3-е место, что лучше, чем второе и третье место у Джона.Тем не менее, Стивен мог быть одинаково хорош, но он участвовал только в одной гонке и должен был понести за это какое-то наказание.

Какие известны алгоритмы для этой проблемы?Есть ли тривиальные решения?Я просто не могу понять это

Answer 1

Вы можете связать позиции с весами (думать об этом как о точках) Например, первая позиция имеет вес 20. Вторая имеет 18. Третья 16 и т. Д.
Мисс участия может относиться к весу -5. Вы можете настроить числа по мере необходимости.

Чтобы найти конечный результат, вы добавляете все веса и сравниваете цифры.

Я думаю, что это должно работать ..

Answer 2

Другой подход заключается в создании порядка верхних узлов, который соответствует порядку предыдущих гонок. Это может быть сделано с помощью алгоритма максимального потока .

Answer 3

Наивным решением было бы иметь какой-то идентификатор для всех игроков. Пройдите по обоим спискам и добавьте все новые идентификаторы, с которыми вы столкнетесь, в отдельный список, например, под названием «Позиции». Установите для всех значений этих идентификаторов какое-то большое число, которое не может быть гоночной позицией, назовите его BIG_VAL (например, 100). Просмотрите первый список и отметьте все позиции как новые значения в списке позиций. Это была только первая гонка, поэтому здесь нет ничего особенного. Затем просмотрите второй список и добавьте результаты второй позиции для этих идентификаторов в список позиций. Для идентификаторов, которые не встречаются, добавьте еще один BIG_VAL к их результату. Теперь в списке будут расставлены расы, все, что осталось, это отсортировать их. Карлу будет 4, Джону будет 5, Фреду будет 8, и так далее в этом списке:

http://bit.ly/fvYtal