给定2d矩阵找到元素的最小和，使得元素从每行和每列中选择一个？

Question

找到n * n二维矩阵的元素的最小和，这样我必须从每一行和每列中选择一个且只有一个元素？ 如

4 12 

6 6 

如果让我选择从1行4我不能选择从1也行12从列1， 我只能从行2列选择6 2.

也照样最低金额会4 + 6 = 10其中6来自第二行第二列

而不是6 + 12 = 18其中6来自第二行第一列列

也4 + 12是不允许的，因为两者都是从同一行

我想动粗，其中有一次，我挑元素从行和列，我不能选择另一个，但这种做法是O(n!) 。

Answer 1

定理：如果数字加上或减去从基质中的任何一个行或列的条目的所有 ，然后选择 元件获得所需要的结果矩阵的最小总和 是相同的元件选择以获得原始矩阵的所需最小总和。

的Hungarian Algorithm（min-cost flow问题的一个特例）使用此定理来选择那些满足于您的问题给定的约束因素：

1. 从 行的所有条目中减去每行中最小的项。
2. 从列的所有条目 中减去每列中的最小值。
3. 通过适当的行和列绘制线条，以便覆盖所有成本矩阵的零条目，并且使用这些线条的最小数量 。
4. 优化性测试
   i。如果覆盖线的最小数量为n，则可以进行最佳的零点分配，我们就完成了。二，如果覆盖线的最小数量小于n，则最佳的零点分配不可能。在这种情况下，请继续步骤5.
5. 确定任何行未涵盖的最小条目。从每个未被覆盖的行减去 此条目，然后将其添加到每个覆盖的 列。回到步骤3

更好地了解见this example。

两者为O（n 4 ）（容易和快速执行）和O（N 3 ）（更难实现）实现进行了详细here说明。