匈牙利算法和多重因素

Question

我有一种情况，我需要来分配人民的几个事件。如果我们只有一个价格的一个因素，这将是好的，但是有一些因素。

首先，一些背景。这是一个非营利组织，促进故事时间的儿童住院因任何原因，因此它们依靠自愿工作这样做。因此，由于他们依靠人们的良好意愿，它们让人们尽可能多的工作，因为人们可以想做的事情，不同而有所变化，如：

• 有些人只能做早晨，以及其他一些人只能做下午；
• 有些人只能星期一和星期四，其他人不能在八月或二月;
• 有些人只能去一个月一次，其他人可以走了4倍(甚至是其他人都是给"优先权"在这些行动，因为他们是经验更丰富，并可以提供要做10次一个月)

因此，我有点儿想出第一二。由于匈牙利算法有关的价格，我会给他们一个愚蠢的高价格的时候，他们可以不去。但是，你会怎么做人？

我以为关于给予他们某种分。沿线的东西:一个人可以做这个曾经一个月的费用的东西喜欢1000点。如果有人可以去10次一个月，这个人费用的100点(1000基础上划分的10个)。此外，这种方式来分发这将是增加的价格，每当一个单独的行动将完成，就像这样(选人有*在其相关的费用):

第一迭代

         | August 1st 2009
Person A | 1000
Person B | 500 *

第二次迭代

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

这将是方式分发由此之间所有的人，给予更多的优先考虑那些可以这样做的好几倍。

什么你认为你会怎么做？

Answer 1

这是一个调度/优化问题，所以关键的问题是"什么样的数量是你想以最大限度地"?我猜你是在找到最大限度的总工作小时数在所有志愿人员没有冲突，受到每个志愿人员的时间安排的约束。你还更优先志愿人员有更多的经验，因此它听起来像你在说"有些志愿者 优选的 在其他人"。

然后，这是一个经典的 二分匹配的问题.例如见p.498 算法的设计手册 (2nd ed.), 由史蒂芬*Skiena.基本的方法是构建一个图顶点代表组的志愿人员和设定的时间隙你正在尝试来填补。边缘的链接志愿人员的有效时间隙。最佳的解决方案是当时最大的可能设定的边缘，那里没有志愿或时间隙是重复的。这是一个匹配。

你的一些志愿者可以做更多比一个槽；这可以被模拟通过复制，志愿人员顶点多次。

如果你想要实现的优先顺序的志愿人员，那么这就有效地增加了一个加权为每个边缘，建模的经验，志愿为这一任务。在这种情况下，为你以为，你会需要的东西喜欢匈牙利算法。如果你可以摆脱没有这一点，然后你可以改变的问题变成一个等效 流程图, 并应用网络流量的算法。这里是一个例子 代码实现两个加权和未加权匹配.

如果你想要的更多细节，包括其他替代办法和更多的联系来实现中，我强烈建议得到自己的副本的算法的设计手册》-这是一个令人惊讶的清晰和实用的参考。