如何找到 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; int 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;
最佳答案
这是一个名为 Assignment problem 的问题.
您可以尝试使用Hungarian algo解决它(如果您需要代码提示,可以通过此 Russian link 找到)。
关于c++ - 如何使用 C++ 查找 N x M 数组内最小值(不同列)的总和?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32799441/