最优解--规划理论

Question

我希望有人解释不同的方法来解决一个简单的问题，然后我将尝试并在PHP中实现它为更广泛的应用程序。

我有五个人在选择谁得到哪个房间，有五个房间，大的，大的，中的，中的和小的。

Person 1 orders the rooms Grand, Large
Person 2 orders the rooms Large, Medium
Person 3 orders the rooms Large, Small
Person 4 orders the room Medium
Person 5 orders the rooms Large, Medium

失踪的房间是他们不感兴趣的房间。

选择谁住每个房间的最公平的方式是什么？

Answer 1

公平性并不总是被很好地定义。

然而，在这种情况下，似乎一个人可以得到他所要求的房间，也可以不得到。因此，人们可以提出一个强有力的论点，即相同数量的人得到他们想要的房间的所有解决方案都是平等的，而更多人得到他们想要的房间的解决方案比少数人得到他们想要的房间的解决方案更公平(因此我们没有给任何一个人优先权)。

在您的示例中，似乎只有一种解决方案，即每个人都可以得到自己想要的房间。因此，这是“最公平”的解决方案。

找到它的算法只是一个深度优先搜索(或者，如果你需要加速，分支定界)，它考虑了所有可能的分配并找到最大的一个。

Answer 2

使用启发式计算每种情况的匹配值。例如，如果一个人仍然没有房间，这个值将是低的或负的。如果每个人都住着他们订的最大的房间，那么价值就是最高的。

为每种情况计算此值，然后取具有最高值的情况。