一道现实中遇到的实际问题，可能是动态规划、图论相关的

把每个人一周的时间用一个14位二进制数表示，一个上午或一个下午代表一位，1空闲，0表示忙碌，然后把两个人的二进制数取交集会得到一个数，用十进制除2求余法得1的个数（也就是重回的时间），用循环把三十个人每两人都求一次，把重回最小的移出去，剩下28人再循环全部求一次，最小的移出去，做15次这样的操作应该能得到总时间最小。 【 在 cod1239 (王小佛) 的大作中提到: 】 : 现在有三十个人，给出每个人每天的课表，要将三十人两两组合成十五对，希望每个人的空闲时间（不上课时间）尽量不重合 : 现实问题就是实验室有点挤，两个人共享一个座位，但要是你不上课我也不上课，俩人不就挤一起了吗，虽然挤一挤也可以忍，但是最好不要挤 : 目标应该是希望总重合时间最小 : ...................

将30个人用顶点表示，如果两个人之间有重复时段，则用一条有权边表示两个顶点间重复时段的数目，如果两个人没有重复时段，则该边权为0. 则原问题是一个图论中的最优分派问题：求上图的一个完美对集使该对集权值和最小。

【 在 nanguohao 的大作中提到: 】 : 将30个人用顶点表示，如果两个人之间有重复时段，则用一条有权边表示两个顶点间重复时段的数目，如果两个人没有重复时段，则该边权为0. : 则原问题是一个图论中的最优分派问题：求上图的一个完美对集使该对集权值和最小。 好像不太对

【 在 nanguohao 的大作中提到: 】 : 将30个人用顶点表示，如果两个人之间有重复时段，则用一条有权边表示两个顶点间重复时段的数目，如果两个人没有重复时段，则该边权为0. : 则原问题是一个图论中的最优分派问题：求上图的一个完美对集使该对集权值和最小。 我不太懂算法，昨天看了一下二分图带权匹配，想到设置A类是这30个人，B类也是这30个人，之间的边是“单向”的，也就是A类中第一个人与第二个人有边，而B类第一个人与A类第二个人无边，这样把问题转化成二分图带权匹配（我没有找到一般图的讲解），不知可行吗？

【 在 jN666 的大作中提到: 】 : 把每个人一周的时间用一个14位二进制数表示，一个上午或一个下午代表一位，1空闲，0表示忙碌，然后把两个人的二进制数取交集会得到一个数，用十进制除2求余法得1的个数（也就是重回的时间），用循环把三十个人每两人都求一次，把重回最小的移出去，剩下28人再循环全部求一次，最小的移出去，做15次这样的操作应该能得到总时间最小。 谢谢！我试一试

这道题可以用递归的思想来解决，和动态规划一样是自底向上递归，但是它并不是动态规划，因为整个问题不满足最优子结构性质，但是问题规模扩大的时候，还是使用了动态规划思想，更新数据。 以下： 令n（n是偶数）个人编号1，2......n,记k（k可以为奇数，也可以为偶数，为奇数时k个人中仅有一个人处于未配对状态，为偶数时，k个人均为两两配对状态）个人在进行两两配对时，最小权之和的状态为{1，2.......k-1,k}（这个记号对应的是一个无向图）。当问题规模为2时，有n(n-1)/2个初始化数据，它可以被存储在一个对称矩阵中，分别对应状态{1,2},{1,3}......{1,n},{2,3},{2,4}......{n-1,n} 下面是算法的操作，以编号顺序依次添加人，问题规模逐渐扩大： 以{1，2}为初始状态，向其中添加3，则需要比较{1，3}，{2，3}和{1，2}的大小，取权值最小得到{1，2，3}。 接下来添加4，则比较（+表示权值相加）{1，4}+{2，3}、{2，4}+{1，3}、{3，4}+{1，2}的值，取最小得到状态{1，2，3，4}。 同时为接下来继续添加做准备，需要计算{1，2，4}、{1，3，4}、{2，3，4}的值，方法与计算{1，2，3}方法相同。 接下来添加5，比较{1，5}+{2，3，4}、{2，5}+{1，3，4}、{3，5}+{1，2，4}、{4，5}+{1，2，3}和{1，2，3，4}（当前是5个人，即奇数个人，5号有可能是空着未匹配的）的大小，取权值之和最小值，得到{1，2，3，4，5}，同时计算{1，2，3，5}、{1，2，4，5}、{1，3，4，5}、{2，3，4，5}。 ...... 当有k-1个人时（问题规模到达k-1时，此时已得到{1，2.......k-1}），向其中添加第k个人，比较{1，k}+{2......k-1}、{2，k}+{1，3......k-1}.......，注意当k是奇数时，还要将{1，2.......k-1}纳入比较范围（因为第k个人可能是空着未匹配的）。此时，当前计算次数为k-1，比较次数为k-1（k是偶数时）或k（k为偶数时）。 为下次添加做准备：需要计算{2.......k-1,k}、{1，3.......k-1,k},总共k-1个，每个的计算次数都是k-2（k是偶数时）或k-1（k是奇数时）。但是添加n（最后一个人）的时候，不需要为下次添加做准备了。 于是，整个算法的总共计算次数和比较次数是n^3量级，即算法时间复杂度为O(n^3)。 整个问题的初始化可以按照楼上的回答解决，但是每添加一个人所要计算的{2，3，4，5.......k}、{1，3，4，5.......k}、{1，2，4，5.......k}、{1，2，3，5.......k}......（即每个最优分配对应的无向图到底是什么，而不仅仅是整体最优分配的权值）的数据结构设计是挺麻烦的，难道给每个最优状态存一个邻接矩阵？好像也不是不行，只是麻烦。另外，楼上的答案，贪心选择性质是不成立的。 以上是我的愚见，请大家批评指正，谢谢。

【 在 cod1239 的大作中提到: 】 : 谢谢！我试一试 我那个想了一下确实不成立

貌似是二分图最大匹配模型？用匈牙利增广路径求看看

这个模型应该是最小边覆盖。至于平均的话可以参考把每条边的长度的上限控制一下