男女搭配，干活不累
表格中每一单元代表纵向女x替换横向男y使得该组提高的效率值。现在将十个女的替换十个男的，每组调整为男女搭配，如何分配调整使得效率增加值最大？（即十组效率增加值之和最大）备注：每个单元格内值应该是处于（0,1），图表中随机函数取整时出现了0，但不影响运算。
KM算法 这个表给的有点独特啊，变换为20男X10女的一个搭配矩阵，KM算法就明显了。
变换方法：行1行2互换，行3行4互换，…，行19行20互换。只换数据列，男下标列不换。 即使穷举也只有10!=3628800种可能，计算机可以做到 发现我说的变换可能有点改变了原题。
变换的等价性基于原男男各组效率相同，但这并不确定。 这题比较有意思。
如果用穷举法，一共有约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
sheng_jianguo 发表于 2019-12-19 17:03
这题比较有意思。
如果用穷举法，一共有约6.70443E+11可能（不仅要考虑女的搭配可能10!，还要考虑 ...
男1男2中有1人替换成女x1,男2男3中有1人替换成女x2,……，男19男20中有1人替换成女x10。使得10个选中的单元格和值最大。 把女1-女10固定，从男1-男20中选10个去分别配对，背包问题 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 于 2020-7-21 18:42 编辑
northwolves 发表于 2020-7-21 16:16
把女1-女10固定，从男1-男20中选10个去分别配对，背包问题
嗯，把女1-女10固定，男1-男20每两个中选出一个再排列（即2^20*10！=3805072588800），组合数还是比较大。背包问题该如何选取呢？贪心不一定是最优解。若要求得最优解，除了枚举，还有没有其他方法。
页:
[1]
2