資料結構
網路
關係資料庫管理系統 (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;
}輸出
The minimum cost is 17
765 次瀏覽
