python - 在 Python 矩阵中，考虑到选择列的成本，如何选择每行一次并获得最低总和？

Question

在我的真实情况下，我有一个68*160的大矩阵。

在这个例子中，我们使用一个较小的。每个数字代表一个成本。

matrix = [[8, 5,      4,    7,   10,    6],
          [8,  None,  4,    12,  None,  2],
          [4,  5,     4,    2,   None,  10],
          [6,  None,  4,    1,   None,  1],
          [2,  5,     None, 3,   2,     10]]

我需要从每一行中准确选择 1 个值。不能选择“无”。

我需要找到成本最低的组合。

困难的部分是，无论从中选择了多少项，对于选择的每一列，都会有 2 的额外成本。

如果我只是遍历每一行并获得最低值，那是行不通的。在这个例子中，我会得到 4、2、2、1、2，但是来自 4 个不同的列。总和为 11+(4*2)=19

如果相反，我从第 2 列得到 4,4，从第 3 列得到 2,1,3，则总和将为 14+(2*2)=18，这已经证明直接从每一行中选择最低的不会'不工作。

我尝试做笛卡尔乘积(矩阵中的所有可能组合)并添加列成本然后进行比较，但这会生成 68^160 个结果，在太阳爆炸时不会完成运行。

我还尝试了一些更复杂的事情，例如遍历每一列并检查值，然后根据需要考虑“事件”或“非事件”，但是很难考虑许多列之间的相互作用。

有什么方法可以优雅地解决这个我没有看到的问题吗？

Answer 1

您可以通过仅考虑最低或低于最低加二的行值来迭代所有可能的解决方案例如，在第一行 [8, 5, 4, 7, 10, 6] 中，您可以考虑将 4、5 作为该行的候选，但选择 6 7 或 8 的成本总是更高选择。

根据您的数据结构，您可以大大减少计算时间。

此外，不是逐行迭代，而是从只有一个最佳解决方案的那些开始，它们可能会突出显示要选择的列并简化您的问题。