gpt4 book ai didi

c++ - 使用动态规划打印矩阵中所有可能路径中总和最小的路径

转载 作者:行者123 更新时间:2023-11-28 01:21:44 25 4
gpt4 key购买 nike

我想打印允许您向右或向下移动的矩阵的最小总和。我能够获得成本,但我不确定如何打印所有可能路径中总和最小的路径。

#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;
}

最佳答案

您可以使用另一个二维数组 std::pair存储达到最优解的路径索引。

重构解决方案

  1. 为了重构解决方案,声明path存储为达到最佳解决方案所采用的最后路径。

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

  1. 在你的内部循环中,每次 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);
    }
    }
  2. 最后,使用 path array 使用递归函数重构解如下(也可以转化为迭代解)

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

演示:here

关于c++ - 使用动态规划打印矩阵中所有可能路径中总和最小的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55887291/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com