数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C语言最小成本路径程序
在这里，我们将解决C语言中的最小成本路径问题。该问题在一个二维矩阵上进行，其中每个单元格都有一个移动成本。我们必须找到一条从左上角到右下角的路径，其移动成本最小。你只能从给定的单元格向下或向右移动到较低的单元格。
为了解决这个问题，动态规划比递归方法更好。
给定成本矩阵 **cost[ ][ ]** 和一个位置 **(m,n)**，我们必须编写一个函数，该函数返回从(0,0)到达(m,n)的最小路径成本。到达(m, n)的路径的总成本是该路径上所有成本的总和（包括起点和终点）。
**假设** — 所有成本均为正数。输入矩阵中不存在负成本循环。
示例
找到到达(2,2)的最小成本路径
成本在图像中给出。路径将是 (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2)。路径值为8 (1 + 2 + 2 + 3)。
**方法** — 创建一个与给定矩阵大小相同的答案矩阵。
自底向上填充此矩阵。
**给定** — arrA[ ][ ]。在每个单元格中，我们有两个选择（向右或向下），我们可以为任何 i,j 单元格选择这两个选择中的最小值。
solution[i][j]=A[0][j] if i=0, 1st row =A[i][0] if j=0, 1st column =A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0
算法答案中采用的方法可以通过应用动态规划来有效地解决此问题。创建一个大小为 m,n 的最小成本路径表并定义：
minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)
显然，
minimumCostPath[0][0] = costMatrix[0][0] minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero
接下来，我们将通过应用与算法中相同的公式来填充最小成本路径矩阵。由于所有先前值都已在最小成本路径矩阵中计算，因此我们不会像在算法答案中那样重新计算这些值。
minimumCostPath[i][j] = costMatrix[i][j] +minimum(minimumCostPath[i - 1][j - 1],minimumCostPath[i - 1][j],minimumCostPath[i][j - 1])
在这里，为了计算 minimumCostPath[i][j]，我们使用 minimumCostPath[i - 1][j - 1]，minimumCostPath[i - 1][j] 和 minimumCostPath[i][j - 1]，因此，这些是从我们到达 minimumCostPath[i][j] 的唯一允许的单元格。最后，我们返回 minimumCostPath[m][n]。
动态规划算法的时间复杂度为 O(mn)。
示例
#include <iostream> using namespace std; int min_(int a, int b, int c){ if (a < b) return (a < c) ? a : c; else return (b < c) ? b : c; } int min_cost(int cost[4][4], int m, int n){ int i, j; int tot_cost[4][4]; tot_cost[0][0] = cost[0][0]; for (i = 1; i <= m; i++) tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0]; for (j = 1; j <= n; j++) tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j]; for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) tot_cost[i][j] = min_(tot_cost[i - 1][j - 1], tot_cost[i - 1][j], tot_cost[i][j - 1]) + cost[i][j]; return tot_cost[m][n]; } int main(){ int cost[4][4] = { { 9, 9, 4 }, { 8, 0, 9 }, {1, 2, 8} }; cout<<" The minimum cost is "<<min_cost(cost, 2, 2); return 0; }
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
The minimum cost is 17
765 次浏览
