algorithm - 动态规划

Question

我的任务是通过蛮力算法制作二维数组的所有可能组合，然后通过其成本从所有组合中找到最佳组合。

例如，如果数组的大小为 4 X 3，并且它有内容让我们说：

1  2  3
4  5  6
7  8  9
10 11 12

那么可能的组合之一可以是

1
4
7
10

相似地

1
4
7
11

...

1
4
7
12

...

1
4
8
10

...

1
4
8
11

...

依此类推，因此所有这些组合。请记住，上述组合存储在二维数组中，并且在没有数字的地方插入了“-”。例如：

1 - -
4 - -
7 - -
10 - -

但由于它是一个二维数组，你不能在其中存储' - '，所以它只会像它一样显示。现在，每个组合都会有一个随机生成的成本。与蛮力一样，首先我找到所有组合，然后选择它的最佳组合。这花了很多时间，例如，如果我的阵列是 10 X 5。

然后我必须做出 5^10 个组合，这是一个巨大的数量，而且很耗时。我实际上希望有人帮助我通过动态编程来替代它。数组的大小可以是 nxm，其中 m 最大可以是 2 或 3，n 最大可以是 1000。提前致谢。

Answer 1

1 - - / - - 6 / - - 9 / - - 12 有效吗？我认为您可能会问的问题是通过这个矩阵最便宜的路径是什么，这是一个标准的动态编程问题，请参阅http://en.wikipedia.org/wiki/Dynamic_programming#Checkerboard。

否则，如果问题仅仅意味着最大总和，那么只需在每一行中做最大值，这应该很清楚，因为每行只能有一个元素。

Answer 2

这个问题的递归（蛮力解决方案）可以如下：

private static void combinations(int[][] matrix, int output[],int row, int col,int index,int n) {

    // base case
    if(row==n)
    {
        printArray(output,row);
        return;
    }

    for(int j=0;j<col;j++)
    {
        output[index] = matrix[row][j];
        combinations(matrix,output, row+1, col,index+1,n);
    }
    return;
}

private static void printArray(int[] output, int row) {
    for(int i=0;i<row;i++)
    {
        System.out.print(output[i]+ ", ");
    }
    System.out.println();
}

在此，函数组合被调用列数次。对于每个列组合，将打印输出数组。我不太确定这个问题的优化。如果有人知道更优化的算法，请分享。