最小的成本總和

我想從起點（0,0）爲這個陣列它等於8的某一點（M，N）計算中給出二維陣列最小的成本總和

#include<iostream> 
#include<limits.h> 
using namespace std; 
#define R 3 
#define C 3 
int Min(int x,int y,int z){ 
    if(x<y){ 
     return (x<z)?x:z; 
    } 
    else 
     return (y<z)?y:z; 
    } 
int mincost(int cost[R][C],int m,int n){ 

    int i,j; 
    int t[R][C]; 
    t[0][0]=cost[0][0]; 
    for(i=1;i<=m;i++) 
     t[i][0]=t[i-1][0]+cost[i][0]; 
    for(j=1;j<=n;j++) 
t[0][j]=t[0][j-1]+cost[0][j]; 
    for(i=1;i<=m;i++){ 
     for(j=1;j<=n;j++){ 
      t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j]); 
     } 
    } 
     return t[m][n]; 

} 

int main(){ 

    int cost[R][C]={{1,2,3}, 
        {4,8,2}, 
        {1,5,3}}; 
    cout<<mincost(cost,2,2)<<endl; 


    return 0; 
}

最小總和，但輸出給我看1，爲什麼？這段代碼有什麼問題？算法在詞語

鑑於成本矩陣成本[] []和一個位置（m，n）的成本[] []，編寫返回最小成本路徑的成本達到（M的函數，正）從（0，0）開始。矩陣的每個單元代表穿過該單元的成本。達到的路徑的總成本（m，n）是該路徑上的所有成本（包括源和目標）的總和。（i，j），（i，j + 1）和（i + 1，j + 1）中的單元格， j + 1）可以遍歷。你可以假設所有成本都是正整數。

來源

2011-11-02 dato datuashvili

你能用言語形容你的算法嗎？這將適用於您的代碼中的註釋塊。 –

我想不出有什麼辦法來解釋結果是8，除了找到最大元素:( –

你添加的描述不是你的*算法*的描述，而是*問題陳述的描述*。 –

我看到這是一個動態編程解決方案。

您在這裏有一個錯字：

t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j]);

它應該是：

t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]) + cost[i][j];

基本上它的工作就像t[i][j] = t[i-1][j-1]。

注意：調試這些問題的一個好方法是打印中間矩陣（這裏是：t）。

來源

2011-11-02 18:43:31

的動態實現，它非常有幫助，非常感謝 –

鑑於T [0] [0] =成本[0] [0] = 1 然後

for(i=1;i<=m;i++){ 
     for(j=1;j<=n;j++){ 
      t[i][j]=Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j]); 
     }

對於i = 1，J = 1

t[1][1] = Min(t[0][0], t[0][1], t[1][0]+cost[1][1]) = Min(1, ...) = 1

對於i = 2 J = 2

t[2][2] = Min(t[1][1], t[1][2], t[2][1]+cost[2][2]) = Min(1, ...) = 1

來源

2011-11-02 18:44:48 pnezis

Min(t[i-1][j-1],t[i-1][j],t[i][j-1]+cost[i][j])

也許應該

Min(t[i-1][j-1],t[i-1][j],t[i][j-1]) +cost[i][j]

只是猜測，它很難讀取你的意圖，但看起來像尋路算法。你的代碼沒有正確地將對角線或水平移動的成本增加，並且由於開始時的成本是1，那也是你的結果。這應該會爲您的示例返回十一個成本。

來源

2011-11-02 18:45:03

最小的成本總和

回答

相關問題