找到n * 3维度的2D数组中元素的最小总和，以便不应在相邻行中选择从行中选择的索引

I have a n*3 2D Array and need to find the min. sum of elements such that:

我有一个n * 3二维数组,需要找到最小值。这些元素的总和:

No rows can be missed out i.e. there should be an element from each row.

不能错过任何行,即每行应该有一个元素。

Only one element can be selected from a row.

一行中只能选择一个元素。

Element selected in a row can't be selected in adjacent rows.

无法在相邻行中选择连续选择的元素。

eg.
10 50 45
30 10 15
70 05 25
09 27 97

例如。 10 50 45 30 10 15 70 05 25 09 27 97

If 10 is selected from row at index 0, 30 can't be selected from row at index 1.

如果从索引0处的行中选择10,则无法从索引1处的行中选择30。

Similarly, if 10 is selected from row at index 1, 05 can't be selected from row at index 2.

类似地,如果从索引1处的行中选择10,则不能从索引2处的行中选择05。

The optimal solution for the array is: 10+15+05+9 = 39

该阵列的最佳解决方案是:10 + 15 + 05 + 9 = 39

Note: Maybe an iteration of Hungarian Algorithm may work for this.

注意:也许匈牙利算法的迭代可能适用于此。

But I don't know how to go with it.

但我不知道该怎么做。

2 个解决方案

#1

Dynamic Programming.

Let DP[i][j] be the minimum sum in the first i rows and the last taken element was from column j.

设DP [i] [j]为前i行中的最小和,最后获取的元素来自列j。

Assuming the array is 1-indexed

假设数组是1索引的

DP[0][j] = 0

DP[i][j] = min(DP[i-1][x])+A[i][j]  (j!=x , 1<=x<=3)

Answer is min(DP[N][j]); the minimum is over 1<=j<=3.

答案是min(DP [N] [j]);最小值超过1 <= j <= 3。

Edit:

    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=3;j++)
        {
            int mn=INF;
            for (int x=1;x<=3;x++)
                if (j!=x) // 3rd rule
                    mn = min(mn,DP[i-1][x]);
            DP[i][j] = mn+A[i][j];
        }
    }
    cout<<min(DP[n][1],min(DP[n][2],DP[n][3]))<<endl;

#2

If no clever problem specific idea comes up,

如果没有巧妙的问题具体想法出现,

I would go with a depth-first-search and cut of the the branch as soon as one of the constraints is violated.

一旦违反其中一个约束条件,我就会进行深度优先搜索并剪切分支。

P.s. Since you can estimate the worst possible value, you could use A*-search which will most likely speed it up.

附:由于您可以估算最差的可能值,因此您可以使用A * -search,这很可能会加快它的速度。

#1