Рубрики

Java-программа для Min Cost Path

Учитывая стоимость матрицы затрат [] [] и позицию (m, n) в стоимости [] [], напишите функцию, которая возвращает стоимость пути минимальной стоимости для достижения (m, n) из (0, 0). Каждая ячейка матрицы представляет собой стоимость прохождения через эту ячейку. Общая стоимость пути для достижения (m, n) представляет собой сумму всех затрат на этом пути (включая как источник, так и пункт назначения). Вы можете перемещаться только вниз, вправо и по диагонали к нижним ячейкам из данной ячейки, то есть из данной ячейки (i, j), ячеек (i + 1, j), (i, j + 1) и (i + 1, j + 1) можно пройти. Вы можете предположить, что все затраты являются положительными целыми числами.

Например, как показано на следующем рисунке, какова минимальная стоимость пути к (2, 2)?

Путь с минимальной стоимостью выделен на следующем рисунке. Путь (0, 0) -> (0, 1) -> (1, 2) -> (2, 2). Стоимость пути составляет 8 (1 + 2 + 2 + 3).

/ * Java-программа для реализации динамического программирования

   задачи Min Cost Path * /

import java.util.*;

  

class MinimumCostPath {

    / * Вспомогательная функция, которая возвращает минимум 3 целых числа * /

    private static int min(int x, int y, int z)

    {

        if (x < y)

            return (x < z) ? x : z;

        else

            return (y < z) ? y : z;

    }

  

    private static int minCost(int cost[][], int m, int n)

    {

        int i, j;

        int tc[][] = new int[m + 1][n + 1];

  

        tc[0][0] = cost[0][0];

  

        / * Инициализировать первый столбец массива общей стоимости (тс) * /

        for (i = 1; i <= m; i++)

            tc[i][0] = tc[i - 1][0] + cost[i][0];

  

        / * Инициализировать первую строку массива tc * /

        for (j = 1; j <= n; j++)

            tc[0][j] = tc[0][j - 1] + cost[0][j];

  

        / * Создаем остаток массива tc * /

        for (i = 1; i <= m; i++)

            for (j = 1; j <= n; j++)

                tc[i][j] = min(tc[i - 1][j - 1],

                               tc[i - 1][j],

                               tc[i][j - 1])

                           + cost[i][j];

  

        return tc[m][n];

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        int cost[][] = { { 1, 2, 3 },

                         { 4, 8, 2 },

                         { 1, 5, 3 } };

        System.out.println("minimum cost to reach" +

                       " (2, 2) = " + minCost(cost, 2, 2));

    }

}
// Этот код предоставлен Панкаджем Кумаром

Выход:

minimum cost to reach (2, 2) = 8

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 6 (Min Cost Path) для более подробной информации!

Рекомендуемые посты:

Java-программа для Min Cost Path

0.00 (0%) 0 votes