男女搭配，干活不累

aimisiyou

表格中每一单元代表纵向女x替换横向男y使得该组提高的效率值。现在将十个女的替换十个男的，每组调整为男女搭配，如何分配调整使得效率增加值最大？（即十组效率增加值之和最大）
备注：每个单元格内值应该是处于（0,1），图表中随机函数取整时出现了0，但不影响运算。

lsr314

KM算法

hujunhua

这个表给的有点独特啊，变换为20男X10女的一个搭配矩阵，KM算法就明显了。
变换方法：行1行2互换，行3行4互换，…，行19行20互换。只换数据列，男下标列不换。

lsr314

即使穷举也只有10!=3628800种可能，计算机可以做到

hujunhua

发现我说的变换可能有点改变了原题。
变换的等价性基于原男男各组效率相同，但这并不确定。

sheng_jianguo

　　这题比较有意思。
　　如果用穷举法，一共有约6.70443E+11可能（不仅要考虑女的搭配可能10!，还要考虑男的从20人选10人组合可能），我试了一下，用我的台式电脑1分钟能计算约241920可能，24小时不间断计算大概需要近2000天才能算完。
　　我想出用以下方法来求最大的十组效率增加值：
1.找出每列的最大值，并选出每列中和本列最大值不超过一常数δ的项，满足所有项至少出现在10行中。（δ不能取得太大，否则选取的项过多，对于本问题δ可取0.05）。
2.用穷举法对选出的项进行计算，得出最大的十组效率增加值以及对应的搭配。
3.分析如果计算出的搭配中，换成没选择的项，十组效率增加值不会大于计算值。
　　对于本问题，下面是我的计算结果：
　最大的十组效率增加值为 2.3700，搭配如下
   男3   女1
   男16  女2
   男20  女3
   男2   女4
   男19  女5
   男18  女6
   男11  女7
   男6   女8
   男12  女9
   男15  女10

aimisiyou

sheng_jianguo 发表于 2019-12-19 17:03
　　这题比较有意思。
　　如果用穷举法，一共有约6.70443E+11可能（不仅要考虑女的搭配可能10!，还要考虑 ...

男1男2中有1人替换成女x1,男2男3中有1人替换成女x2,……，男19男20中有1人替换成女x10。使得10个选中的单元格和值最大。

northwolves

把女1-女10固定，从男1-男20中选10个去分别配对，背包问题

sheng_jianguo

aimisiyou 发表于 2020-7-20 22:42
男1男2中有1人替换成女x1,男2男3中有1人替换成女x2,……，男19男20中有1人替换成女x10。使得10个选中的单 ...

问题不清楚，如果是：
男1男2中有1人替换成女1,男3男4中有1人替换成女2,……，男19男20中有1人替换成女10。使得10个选中的单元格和值最大。
则比较简单，两个中取大值即可：
最大的十组效率增加值为 1.7725，搭配如下
   男1   女1
   男3   女2
   男5   女3
   男7   女4
   男10  女5
   男11  女6
   男14  女7
   男15  女8
   男18  女9
   男20  女10

aimisiyou

northwolves 发表于 2020-7-21 16:16
把女1-女10固定，从男1-男20中选10个去分别配对，背包问题

嗯，把女1-女10固定，男1-男20每两个中选出一个再排列（即2^20*10！=3805072588800），组合数还是比较大。背包问题该如何选取呢？贪心不一定是最优解。若要求得最优解，除了枚举，还有没有其他方法。