a**********s
发帖数: 588 | 1 【 以下文字转载自 CS 讨论区 】
发信人: algorithmics (沙盘推演), 信区: CS
标 题: 问一个算法: 婚姻介绍所问题
发信站: BBS 未名空间站 (Fri Sep 11 01:47:12 2009, 美东)
婚姻介绍所登记有n位男士和n位女士, 都不是gay, 都希望找异性, 而且均遵循一夫一
妻的传统.
每人的登记表包含一个有m个问题的问卷, 每个问题都是是非题, 答案是Y或者N
婚介所用通过对这m个问题的相同答案的个数来衡量一对男女的和谐程度.
如何配对这n对男女, 使得总体的和谐程度最高, 复杂度是多少? | c*****t
发帖数: 1879 | 2 See http://en.wikipedia.org/wiki/Assignment_problem
【在 a**********s 的大作中提到】
: 【 以下文字转载自 CS 讨论区 】
: 发信人: algorithmics (沙盘推演), 信区: CS
: 标 题: 问一个算法: 婚姻介绍所问题
: 发信站: BBS 未名空间站 (Fri Sep 11 01:47:12 2009, 美东)
: 婚姻介绍所登记有n位男士和n位女士, 都不是gay, 都希望找异性, 而且均遵循一夫一
: 妻的传统.
: 每人的登记表包含一个有m个问题的问卷, 每个问题都是是非题, 答案是Y或者N
: 婚介所用通过对这m个问题的相同答案的个数来衡量一对男女的和谐程度.
: 如何配对这n对男女, 使得总体的和谐程度最高, 复杂度是多少?
| a**********s
发帖数: 588 | |
|
