Печать пути с минимальной суммой среди всех возможных путей в матрице с использованием динамического программирования - PullRequest
Новая
       9

Печать пути с минимальной суммой среди всех возможных путей в матрице с использованием динамического программирования

0 голосов
/ 28 апреля 2019

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

#include <iostream>
    #include <string>
    #include <algorithm>
    using namespace std;

    #define M 3
    #define N 3

    int findMinCost(int cost[M][N])
    {
        int T[M][N];

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                T[i][j] = cost[i][j];

                if (i == 0 && j > 0)
                    T[0][j] += T[0][j - 1];

                else if (j == 0 && i > 0)
                    T[i][0] += T[i - 1][0];

                else if (i > 0 && j > 0)
                    T[i][j] += min(T[i - 1][j], T[i][j - 1]);

            }
        }

        return T[M - 1][N - 1];
    }

    int main()
    {
        int cost[M][N] =
        {
            { 9,-2,10 },
            { 15,23,-10 },
            { 40,16,2 },
        };

        cout << "The minimum cost is " << findMinCost(cost);

        return 0;
    }

1 Ответ

2 голосов
/ 28 апреля 2019

Вы можете использовать другой двумерный массив std::pair для хранения индексов пути, выбранного для достижения оптимального решения.

Восстановление решения

  1. Для восстановлениярешение, объявите path для хранения последнего пути, выбранного для достижения оптимального решения.

std::pair<int,int> path[M][N]

В вашем внутреннем цикле вычисляется каждый раз T[i][j], также вычисляется path[i][j]

if (i == 0 && j > 0) {
  T[0][j] += T[0][j - 1];
  path[0][j] = std::make_pair(0, j - 1);
}
else if (j == 0 && i > 0) {
  T[i][0] += T[i - 1][0];
  path[i][0] = std::make_pair(i - 1, 0);
}
else if (i > 0 && j > 0) {
  if (T[i - 1][j] < T[i][j - 1]) {
    T[i][j] += T[i - 1][j];
    path[i][j] = std::make_pair(i - 1, j);
  } else {
    T[i][j] += T[i][j - 1];
    path[i][j] = std::make_pair(i, j - 1);
  }
}

Наконец, используя массив path, реконструируйте решение, используярекурсивная функция выглядит следующим образом (ее также можно преобразовать в итеративное решение) 

void printPath(int i, int j, std::pair<int,int> path[M][N], int cost[M][N])
{
  if (!i && !j) {
    cout << cost[i][j] << ' ';
    return;
  }
  printPath(path[i][j].first, path[i][j].second, path, cost);
  cout << cost[i][j] << ' ';
}

Демо: здесь

...