c++ - 如何使用 C++ 在 N x M 数组中找到最小值(不同列)的总和？

Question

如何找到 N x M 数组中每一行的求和最小值和非重复列？

对于一个简单的 3x3 示例问题:

1.000000 2.000000 2.236068
0.000000 1.000000 3.162278
1.000000 0.000000 4.123106

答案是2.236068

第 1 行第 3 列 + 第 2 行第 1 列 + 第 3 行第 2 列 =
2.236068。

谢谢。

---

错误代码:诠释 n = 4; 整数 m = 4;

int a[4][4] =
{
    { 3, 2, 1, 4 },
    { 1, 0, 3, 4 },
    { 1, 2, 3, 4 },
    { 1, 2, 3, 4 }
};

vector<int> u (n+1), v (m+1), p (m+1), way (m+1);

for (int i=1; i<=n; ++i)
{
    p[0] = i;
    int j0 = 0;
    vector<int>  minv (m+1, INT_MAX);
    vector<char> used (m+1, false);
    do {
        used[j0] = true;
        int i0 = p[j0],  delta = INT_MAX,  j1;
        for (int j=1; j<=m; ++j)
            if (!used[j])
            {
                int cur = a[i0][j]-u[i0]-v[j];
                if (cur < minv[j])
                    minv[j] = cur,  way[j] = j0;
                if (minv[j] < delta)
                    delta = minv[j],  j1 = j;
            }
        for (int j=0; j<=m; ++j)
            if (used[j])
                u[p[j]] += delta,  v[j] -= delta;
            else
                minv[j] -= delta;
        j0 = j1;
    }
    while (p[j0] != 0);

    do
    {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
    }
    while (j0);
}

vector<int> ans (n+1);
for (int j=1; j<=m; ++j)
    ans[p[j]] = j;

Answer 1

这是一个称为 Assignment problem 的问题.

您可以尝试使用 Hungarian algo 解决它(如果您需要代码提示，可以通过此 Russian link 找到)。