Dynami c программирование с битовой маскировкой

Question

Есть N мужчин и N женщин, оба пронумерованы 1,2,…, N

.

Для каждого i, j (1≤i, j≤N) совместимость мужчины и женщины j задается как целое число ai, j. Если ai, j = 1, мужчина i и женщина j совместимы; если ai, j = 0

, это не так.

Таро пытается составить N пар, каждая из которых состоит из мужчины и женщины, которые совместимы. Здесь каждый мужчина и каждая женщина должны принадлежать ровно к одной паре.

как изобразить состояние дп?

Answer 1

Итак, у вас есть неориентированный двудольный граф, и вы хотите получить полное (идеальное) соответствие.

Его можно найти с помощью Алгоритм Форда-Фулкерсона (примечание: он жадный, а не DP)

Пример применения ДП к задаче идеального сопоставления - Алгоритм Хопкрофта-Карпа