Путь с максимальным средним значением

sri vishnu

9 августа 2021 в 05:19

import java.util.Scanner;

public class maxAvgPath {
    public static void main(String [] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] c = new int[n+1][n+1];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                c[i][j]=sc.nextInt();
        }
    }
   float sum = c[0][0];
   float m = 0;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
                if (c[i][j + 1] < c[i + 1][j]) {
                    sum = sum + c[i + 1][j];
                    m++;
                    

                } else {
                    sum = sum + c[i][j + 1];
                    m++;
                    
                }
        }
    }

    System.out.println((sum/m));
}
}

Дана квадратная матрица размера N*N, где каждая ячейка связана с определенной стоимостью. Путь определяется как определенная последовательность ячеек, которая начинается с верхней левой ячейки, перемещается только вправо или вниз и заканчивается в нижней правой ячейке. Мы хотим найти путь с максимальным средним среди всех существующих путей. Среднее значение рассчитывается как общая стоимость, деленная на количество посещенных ячеек на пути. Вход: Матрица = [1, 2, 3, 4, 5, 6, 7, 8, 9] Выход: 5,8 Путь с максимальным средним: 1 -> 4 -> 7 -> 8 -> 9 Сумма пути равна 29, а среднее значение равно 29/5 = 5,8

Но я получаю неверный результат. Может ли кто-нибудь сказать, где моя ошибка?

java
matrix

Источник

Поделиться Скопировать ссылку Скопировано

U. Windl

9 августа 2021 в 08:01

Кто такие «мы»? Получилось ли у вас перефразировать ваше задание?

sri vishnu

15 февраля 2022 в 15:13

Что это значит?

Ответы (1)

Silviu Burcea

9 августа 2021 в 06:22

Ваш m всегда должен быть 2 * n - 1. Независимо от выбранного пути, вы всегда будете двигаться вправо или вниз, начиная с верхнего левого угла. У вас есть n - 1 строк и n - 1 столбцов, поэтому вы двигаетесь вправо ровно n - 1 и двигаетесь вниз ровно n - 1 раз. Всего, считая верхнее левое, у вас есть 1 + (n - 1) + (n - 1) числа на вашем идеальном пути. Таким образом, вы ищете не максимальное среднее значение, а максимальную сумму.

Ваши циклы не совсем синхронизированы с тем, что вы пытаетесь сделать. Скажем, для данной матрицы, когда i = 0, j is 0, вы обнаруживаете, что 4 больше, чем 2. Вы выбираете 4, m[1][0], а затем вы должны проверить максимум m[1][1] и m[ 2][0] ... но ваш цикл переходит к ... i = 0, j = 1, что позволяет вам проверить m[1][2] и m[1][1].

Вы также используете жадный подход, который не всегда дает наилучший результат, т.е. [1 2 9, 3 4 9, 5 2 9], ваш алгоритм выберет 1, переместится вниз к 3 и 5, затем вправо к 2 и 9, что даст вам в общей сложности 20. Однако идеальный путь — это 1, прямо к 2 и 9, затем до 9 и 9, всего 30.

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

например. для [1 2 9, 3 4 9, 5 2 9] вы инициализируете свою матрицу суммы с помощью 0 и начинаете навигацию.

Для sum[0][0] существует только одна возможная сумма, которая равна m[0][0]. Это продолжается для всей 1-й строки, поэтому ваша матрица сумм теперь [1 3 12, 0 0 0, 0 0 0]. Для sum[1][0] также существует только одна возможная сумма, идущая вниз от m[0][0], поэтому sum[1][0] равна m[0][0] + m[1][ 0]. И тут начинается самое интересное.

Для суммы[1][1] вам нужно выбрать между суммой[0][1] и суммой[1][0] и добавить m[1][1]. Вы, конечно, выберете sum[1][0] (на самом деле это m[0][0] + m[1][0]) и прибавите к нему m[1][1], так что sum[1][0] 1] равно 8. Следовательно, если ваш максимальный путь когда-либо ведет к r1c1, вы знаете, что на данный момент выбрали максимально возможную сумму.

Я также выделю следующий шаг, sum[1][2], где вам нужно выбрать между sum[0][2] и sum[1][1] и добавить m[1][2]. Мы знаем, что sum[0][2] равно 12, sum[1][1] равно 8, поэтому, если наш путь когда-либо достигает ячейки r1c2, мы знаем, что нам нужно полностью выбрать первую строку, а затем вместо этого двигаться вниз (m[ 0][0], m[0][1], m[0][2], m[1][2]) перемещения вниз и выбора следующей строки (m[0][0], m[1 ][0], m[1][1], m[1][2]), поэтому ваша текущая максимальная сумма в sum[1][2] равна 21, а ваша матрица сумм равна [1 3 12, 4 8 21 , 0 0 0].

Последняя строка такая же:

sum[2][0] = sum[1][0] + m[2][0]
sum[2][1] = max(sum[1][1], sum[2][0]) + m[2][1]
sum[2][2] = max(sum[1][2], sum[2][1]) + m[2][2]

Ваша матрица сумм в конечном итоге становится [ 1 3 12, 4 8 21, 9 11 30 ], поэтому ваш максимум 30. Вы выбрали 2 * 3 - 1 = 5 чисел, поэтому ваше среднее значение равно 6.

Иллюстрация матрицы суммы также интересна:

1  3 12
4  8 21
9 11 30

Если вы когда-нибудь захотите определить, какой путь вы выбрали из верхнего левого угла в нижний правый, вам просто нужно следовать суммам в порядке убывания (учитывая правило движения вправо или вниз). ), 30 -> 21 -> 12 -> 3 -> 1.

Я оставлю часть кодирования в качестве упражнения, у вас есть все необходимые детали.

(извините за неправильное форматирование и длинный текст)

Поделиться Скопировать ссылку Скопировано