Рубрики

Программа C для Min Cost Path

C Программы, Динамическое программирование

Учитывая стоимость матрицы затрат [] [] и позицию (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).

/ * Динамическое программирование реализации проблемы MCP * /
#include <limits.h>
#include <stdio.h>
#define R 3
#define C 3

  

int min(int x, int y, int z);

  

int minCost(int cost[R][C], int m, int n)

{

    int i, j;

  

    // Вместо следующей строки мы можем использовать int tc [m + 1] [n + 1] или

    // динамически распределяем памятки для экономии места. Следующая строка

    // используется для упрощения программы и ее работы на всех компиляторах.

    int tc[R][C];

  

    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];

}

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

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

{

    if (x < y)

        return (x < z) ? x : z;

    else

        return (y < z) ? y : z;

}

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

int main()

{

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

                       { 4, 8, 2 },

                       { 1, 5, 3 } };

    printf(" %d ", minCost(cost, 2, 2));

    return 0;

}

Выход:

8

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

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

Программа C для Min Cost Path

0.00 (0%) 0 votes