假设给定了一个集合A = {1，2，...，m}和一个集合B = {1,2，...，n}，这样就必须将集合A中的每个元素分配给某个来自集合A的每个元素i和来自集合B的每个元素j的以下参数是已知的:
对于每个固定的i，tij的所有值Tij(对于所有j的值)都是不同的。 m和n是大于0的整数，其他变量是非负实数。
根据集合的偏好tij(或Tij)将集合A中的元素分配给元素B中的元素。例如，如果tij
如果将元素i分配给元素j，则将成本Sij添加到分配给元素j的总成本中，即Cj = Cj + Sij。令Max为所有成本Cj中的最大值，而Min为所有成本Cj中的最小值。目的是选择赋值元素i到元素j的哪个首选项采用Tij的值，以及哪个首选项采用tij的值，使得:
我认为有一些动态编程算法，但是我不确定。是否有人知道如何通过DP方法或其他方法解决此问题？但是，它可能不是多项式，但我认为是。
例子。令m = 3，n = 2，即A = {1,2,3}和B = {1,2,3}。令r = 2，矩阵S，t和T为
|5 9| |1 3| |10 7|
S = |7 1|, t = |4 2|, T = | 5 4|.
|8 4| |3 4| | 9 12|
在最小化Max值的情况下，解决方案等于5。可以构造类似的示例以最小化Max-Min。
最佳答案
问题是NP难，可以通过将Partition减少为NP来显示。
假设我们有一个算法M，可以最佳地解决您的问题。
给定一个Partition实例X = {x1，x2，...，xm}，并想找到S的分区为两个子集，它们的和差最小。让我们定义n = 2，Sij = xi，tij = -j，Tij = j。现在，我们仅遍历所有可能的r并调用M作为子例程，以找到Max的全局最小值。我们可以证明，导致最小值Max的分配是X的最优2分区。
由于您不是使用整数成本而是实际成本，并且问题可能会在n> 2时变得更难(我们还可以通过简单的方法将n个垃圾箱减少Bin packing到您的问题中)，因此似乎不太可能除非P = NP，否则甚至存在针对您问题的拟多项式解。您应该考虑使用启发式方法来获得良好的近似解。一个很好的起点是查看Bin装箱的近似方案，并尝试使其适应您的问题。也许简单的第一手方法就足以满足您的需求。您还应该记住两点:
对于固定的i，