给定 2d 矩阵找到元素的最小总和，以便从每一行和每一列中选择一个元素？
Given 2d matrix find minimum sum of elements such that element is chosen one from each row and column?
找到 n*n 二维矩阵元素的最小总和，以便我必须从每一行和每一列中选择一个且只能选择一个元素？
例如
4 12
6 6
如果我从第 1 行中选择 4，我将无法从第 1 行中选择 12，也无法从第 1 列中选择，
我只能从第2行第2列中选择6个
所以同样最小总和将是 4 + 6 = 10 其中 6 来自第二行第二列
而不是 6 + 12 = 18 其中 6 来自第二行第一列
也不允许 4 + 12，因为两者都来自同一行
我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是 O(n!)
.
定理：如果一个数被加到或减去所有
矩阵的任何一行或一列的条目，
然后元素 selected 以获得结果矩阵所需的最小总和
是相同的元素 selected 以获得原始矩阵所需的最小总和。
Hungarian Algorithm (a special case of min-cost flow 问题）使用此定理 select 那些满足问题中给定约束的元素：
- 从每行的所有条目中减去最小的条目
行。
- 从所有条目中减去每列中最小的条目
其专栏。
- 通过适当的行和列画线，以便所有
成本矩阵的零个条目被覆盖并且最小数量
使用了这样的行。
- 最优性测试
一世。如果覆盖线的最小数量是 n，则可以对零进行最优分配，我们就完成了。
二.如果覆盖线的最小数量小于 n，则最优
零分配尚不可能。在这种情况下，继续执行步骤 5。
- 确定未被任何行覆盖的最小条目。减去
这个条目从每个未覆盖的行，然后将它添加到每个覆盖
柱子。 Return 到步骤 3。
请参阅 this example 以获得更好的理解。
O(n4)（实现简单快捷）和 O(n3)（更难实现）实现被详细解释here。
找到 n*n 二维矩阵元素的最小总和，以便我必须从每一行和每一列中选择一个且只能选择一个元素？ 例如
4 12
6 6
如果我从第 1 行中选择 4，我将无法从第 1 行中选择 12，也无法从第 1 列中选择，
我只能从第2行第2列中选择6个
所以同样最小总和将是 4 + 6 = 10 其中 6 来自第二行第二列
而不是 6 + 12 = 18 其中 6 来自第二行第一列
也不允许 4 + 12，因为两者都来自同一行
我想到了蛮力，一旦我从行和列中选择元素，我就无法选择另一个，但这种方法是 O(n!)
.
定理：如果一个数被加到或减去所有 矩阵的任何一行或一列的条目， 然后元素 selected 以获得结果矩阵所需的最小总和 是相同的元素 selected 以获得原始矩阵所需的最小总和。
Hungarian Algorithm (a special case of min-cost flow 问题）使用此定理 select 那些满足问题中给定约束的元素：
- 从每行的所有条目中减去最小的条目 行。
- 从所有条目中减去每列中最小的条目 其专栏。
- 通过适当的行和列画线，以便所有 成本矩阵的零个条目被覆盖并且最小数量 使用了这样的行。
- 最优性测试
一世。如果覆盖线的最小数量是 n，则可以对零进行最优分配，我们就完成了。
二.如果覆盖线的最小数量小于 n，则最优 零分配尚不可能。在这种情况下，继续执行步骤 5。 - 确定未被任何行覆盖的最小条目。减去 这个条目从每个未覆盖的行，然后将它添加到每个覆盖 柱子。 Return 到步骤 3。
请参阅 this example 以获得更好的理解。
O(n4)（实现简单快捷）和 O(n3)（更难实现）实现被详细解释here。