How to find the summation of smallest value (distinct column) inside a N x M array using C++?

Question

How to find the summation smallest value and distinct column for each row inside a N x M array?

For an simple 3x3 example question:

1.000000 2.000000 2.236068
0.000000 1.000000 3.162278
1.000000 0.000000 4.123106

The answer is 2.236068

Row 1 Column 3 + Row 2 Column 1 + Row 3 Column 2 =
2.236068.

Thanks.

---

Wrong Code: int 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;

Answer 1

This is some brute force example (not related with x1Mike7x algo mentions, which you probably should look into). Complexity for a N x M matrix is O(N! x M), take care:

#include <iostream>
#include <algorithm>

using namespace std;

template <class T, int N, int M>
T sum_candidates(const int (&v)[N], const T(&m)[N][M]) {
    T sum = 0;
    for (int i = 0; i != N; ++i) {
        sum += m[i][v[i]];
    }
    return sum;
}

template <class T, int N, int M>
T minor_sum(const T (&m)[N][M], int(&best)[N]) {
    int v[N];
    for (int i = 0; i != N; ++i) {
        v[i] = i;
    }

    bool first_iteration = true;
    T current_sum, minor_sum;
    do {
        current_sum = sum_candidates(v, m);
        if (first_iteration) {
            minor_sum = current_sum;
            first_iteration = false;
            copy(v, v + N, best);
        } else {
            if (current_sum < minor_sum) {
                minor_sum = current_sum;
                copy(v, v + N, best);
            }
        }
    } while (next_permutation(v, v + N));

    return minor_sum;
}

int main() {
    const double m[3][3] = {
        {1.000000, 2.000000, 2.236068},
        {0.000000, 1.000000, 3.162278},
        {1.000000, 0.000000, 4.123106},
    };
    int best_in_row[3];

    const double sum = minor_sum(m, best_in_row);

    cout << "minimal sum: " << sum << "\nchosen ones: ";
    for (int i = 0; i != sizeof(best_in_row)/sizeof(best_in_row[0]); ++i) {
        cout << "M["<< i << "][" << best_in_row[i] << "] ";
    }
    cout << endl;
}

Answer 2

This is a problem which called as Assignment problem.

You could try resolve it using Hungarian algo (if you need a hints for the code, you can find it by this Russian link).