Найти минимальную сумму элементов в матрице - PullRequest
Новая
       11

Найти минимальную сумму элементов в матрице

0 голосов
/ 06 февраля 2020

Учитывая матрицу, найдите минимальную сумму элементов, такую, что элемент выбирается из каждой строки, и соседний элемент не должен приходить из одного столбца. Предположим, что матрица имеет только 3 столбца. 

example 1:
[[1, 2, 3], 

 [1, 2, 3], 

 [3, 3, 1]]

minimum sum = 1 + 2 + 1 = 4  // matrix[0][0] + matrix[1][1] + matrix[2][2] or matrix[0][1] + matrix[1][0] + matrix[2][2]

example 2:
[[1, 100, 1], 

 [2, 99, 30],

 [100, 12, 13]]

minimum sum = 1 + 2 + 12 = 15 // matrix[0][2] + matrix[1][0] + matrix[2][1]

example 3:
[[1, 2, 3], 

 [2, 5, 4],

 [2, 3, 1],

 [1, 6, 3]]

minimum sum = 2 + 2 + 1 + 1 = 6 // matrix[0][1] + matrix[1][0] + matrix[2][2] + matrix[3][0]

Вот мой код: 

    public static int minCost(List<List<Integer>> matrix) {
        // Write your code here
        int rows = matrix.size();

        int[] cost = findMin(matrix.get(0), -1);
        int total = cost[0];

        for (int i = 1; i < rows; i++){
            List<Integer> row = matrix.get(i);
            cost = findMin(row, cost[1]);
            total += cost[0];
        }
        return total;
    }

    private static int[] findMin(List<Integer> row, int col){
        int[] ans = new int[2];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < row.size(); i++) {
            if (i == col){
                continue;
            }
            if (row.get(i) < min) {
                min = row.get(i);
                ans[0] = min;
                ans[1] = i;
            }
        }
        return ans;
    }

Я первоначально подошел к этому вопросу с Greedy, который должен найти минимальный элемент в строке, а столбец элемента отличается от предыдущего элемента.

Этот метод не удовлетворяет примерам 2 и 3. Я думаю, что динамическое c программирование было бы способом решения этой проблемы, но я не уверен, как построить часть mem. Как на самом деле решить эту проблему с помощью Dynami c программирования? Заранее спасибо!

1 Ответ

1 голос
/ 06 февраля 2020

Да, вам нужно идентифицировать рекурсивную структуру, как вы указали в одном из ваших комментариев.

Вы можете указать следующее: Допустим, вы находитесь в строке row и в предыдущем выбранном вами столбце. было prevcol, тогда вам нужно выбрать значение, которого нет в предыдущем столбце, и выполнить рекурсию по оставшимся строкам, и получить минимум всех таких значений, т.е. каждый раз, когда вы выбираете столбец, который не является предыдущим, и рекурсировать по оставшимся строкам, указание выбранного столбца prev было тем столбцом, который вы выбрали только сейчас.

Посмотрите на это рекурсивное уравнение, чтобы понять больше:

f( arr, row, prevcol ) = minimum of ( for all col not equal to prevcol ( arr[row][col] + f( arr, row + 1, col ) )

вы видите, как задать следующий строка и предыдущий столбец, выбранные в вызове f(arr, row +1, col )?

Базовое условие: если row == arr.length то есть строк не осталось, то результатом будет 0.

И вы запомните значения, которые вы получить для каждой комбинации row и prevcol

Java код будет: 

private static int f( int[][] arr, int row, int prevCol ) {
    if ( row == arr.length ) return 0;

    int C = arr[row].length;
    if ( dp[row][prevCol+1] != Integer.MAX_VALUE ) return dp[row][prevCol+1];
    int res = Integer.MAX_VALUE;
    for ( int j = 0; j < C; j++ ) {
      if ( j != prevCol ) {
        int val = arr[row][j] + f ( arr, row + 1, j );
        res = Math.min ( res, val );
      }
    }
    dp[row][prevCol+1] = res;
    return res;
  }

Вам необходимо создать массив dp, например: 

dp = new int[arr.length][arr[0].length+1];
for ( int[] r : dp ) Arrays.fill(r, Integer.MAX_VALUE);

, и вы вызываете функцию следующим образом: f( arr, 0, -1 ), где 0 - это начало row, а -1 - это prevcol. Поскольку prevcol начинается с -1, вам необходимо сохранить значение в dp[row][prevcol+1]

, а также для вашего третьего примера ответом будет 6, а не 9. 

row = 0, col = 1 : 2
row = 1, col = 0 : 2
row = 2, col = 2 : 1
row = 3, col = 0 : 1
2 + 2 + 1 + 1 = 6
...