資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究最小代價路徑
給出了一個不同成本的矩陣。此外，還提供了目標單元格。我們必須找到從起始單元格 (0, 0) 到達目標單元格的最小代價路徑。
矩陣的每個單元格表示透過該單元格的遍歷成本。
從一個單元格出發，我們無法移動到任何地方，我們可以向右移動，也可以向下移動，或者向右下角對角線移動，以到達目的地。
輸入和輸出
Input: The cost matrix. And the destination point. In this case the destination point is (2, 2). 1 2 3 4 8 2 1 5 3 Output: The minimum cost to reach to the destination from (0, 0). The minimum cost is 8.
演算法
minCostPath(destX, destY, cost)
輸入 − 目標的 (x, y) 位置和成本矩陣。
輸出 − 到達目標的最小成本。
Begin define matrix totalCost, whose order is same as cost matrix totalCost[0, 0] = cost[0, 0] for i := 1 to destX, do totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0] done for j := 1 to destY, do totalCost[0, j] := totalCost[0, j-1] + cost[0, j] done for all places (i, j) from (1, 1) to (destX, destY), do totalCost[i, j] := minimum of totalCost[i-1, j-1], totalCost[i-1, j] and (totalCost[i, j-1] + cost[i,j]) done return totalCost[destX, destY] End
示例
#include<iostream>
#define ROW 3
#define COL 3
using namespace std;
int cost[ROW][COL] = {
{1, 2, 3},
{4, 8, 2},
{1, 5, 3}
};
int min(int a, int b, int c) {
return (a<b)?((a<c)?a:c):((b<c)?b:c);
}
int minCostPath(int destX, int destY) {
int totalCost[ROW][COL];
totalCost[0][0] = cost[0][0];
for (int i = 1; i <= destX; i++)
totalCost[i][0] = totalCost[i-1][0] + cost[i][0]; //set first col of totalCost array
for (int j = 1; j <= destY; j++) //set first row of totalCost array
totalCost[0][j] = totalCost[0][j-1] + cost[0][j];
for (int i = 1; i <= destX; i++) //for second row and column to all
for (int j = 1; j <= destY; j++)
totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i- 1][j], totalCost[i][j-1]) + cost[i][j];
return totalCost[destX][destY];
}
int main() {
cout << "Minimum Cost: "<< minCostPath(2, 2); //destination (2, 2)
return 0;
}輸出
Minimum Cost: 8
更新時間：17-Jun-2020
553 次瀏覽
廣告