mxn矩阵的最少k个元素，限制none个元素可以在同一个row/column
Minimum k elements of an mxn matrix, with the restriction that none of the elements can be in the same row/column
我有一个动态规划（可能是贪心的）问题。
令 A 为 mxn 矩阵。设 k 是一个整数，使得 k ≤最小{m,n}.
找到 A 的 k 个元素，使得这 k 个元素中的每一个都在其唯一的列和行中；并且这k个元素的和是最小的。
换句话说，我想从A中挑选出k个元素，使得它们的总和最小；但是如果我 select A2,3 那么我不能 select A2,6 或 A4,3.
贪婪的方法似乎是 selectA 中的最小元素，删除它的行和列，并重复直到 A 是 'depleted'。但是，在这种情况下，我无法证明贪婪选择 属性，或者如果它 有 贪婪选择 属性.
我也不知道如何为 DP 解决方案构建 table。
如果这个问题之前已经提出过并且有具体的名称，能否分享一下？
贪心不割。你需要匈牙利算法机器。可以考虑创建 n-k 新行和 m-k 新列，使新行新列条目非常没有吸引力，而其他新条目非常有吸引力。然后找到一个最小成本的解决方案，使行与列一对一匹配，并丢弃包含新行或新列的对。
在实际操作中，会有更好的实现，但描述它需要我回顾一下HA的细节。
贪心算法不会给出最优解。假设 A11 = 0，A12 = A21 = 1，其他所有值 = 1000。通过取 A12、A21 和任何 k-2 个其他值，总计 1000k - 1998 找到最小和。选择 A11 = 0 首先迫使您选择 k -1 个值为 1000，总计 1000k - 999。
我有一个动态规划（可能是贪心的）问题。
令 A 为 mxn 矩阵。设 k 是一个整数，使得 k ≤最小{m,n}.
找到 A 的 k 个元素，使得这 k 个元素中的每一个都在其唯一的列和行中；并且这k个元素的和是最小的。
换句话说，我想从A中挑选出k个元素，使得它们的总和最小；但是如果我 select A2,3 那么我不能 select A2,6 或 A4,3.
贪婪的方法似乎是 selectA 中的最小元素，删除它的行和列，并重复直到 A 是 'depleted'。但是，在这种情况下，我无法证明贪婪选择 属性，或者如果它 有 贪婪选择 属性.
我也不知道如何为 DP 解决方案构建 table。
如果这个问题之前已经提出过并且有具体的名称，能否分享一下？
贪心不割。你需要匈牙利算法机器。可以考虑创建 n-k 新行和 m-k 新列，使新行新列条目非常没有吸引力，而其他新条目非常有吸引力。然后找到一个最小成本的解决方案，使行与列一对一匹配，并丢弃包含新行或新列的对。
在实际操作中，会有更好的实现，但描述它需要我回顾一下HA的细节。
贪心算法不会给出最优解。假设 A11 = 0，A12 = A21 = 1，其他所有值 = 1000。通过取 A12、A21 和任何 k-2 个其他值，总计 1000k - 1998 找到最小和。选择 A11 = 0 首先迫使您选择 k -1 个值为 1000，总计 1000k - 999。