如何打印從動態編程技術開始的最佳路徑

下面是包含+ ve和-ve數字的數組的標準maxsum的代碼。我認爲，下面的程序是正確的。 Bot如何打印最佳路徑？通過保持一個指向最佳父母的指針，我可以輕鬆地向後打印路徑，但是如何向前打印它，最好不要額外記帳。如何打印從動態編程技術開始的最佳路徑

#include <stdio.h> 

main() 
{ 
    int array[]={5,-5,3,4,-2}; 
    int n=5; 
    int i; 
    int maxsumendingat[n]; 
    int parent[n]; 
    int maxsum=-9999; // better way to code? 
    int optimallastindex; 

    maxsumendingat[0]=array[0]; 

    for(i=1;i<n;i++) 
    { 
     if(maxsumendingat[i-1] <= 0) 

     { 
      maxsumendingat[i]=array[i]; 
      parent[i]=i; 
     } 
     else 
     { 
      maxsumendingat[i]=array[i]+maxsumendingat[i-1]; // also keep backtracking info 
      parent[i]=i-1; 
     } 
    } 

    // now print results 
    for(i=0;i<n;i++) 
    { 
     if(maxsum < maxsumendingat[i]) 
     { 
     maxsum=maxsumendingat[i]; 
     optimallastindex=i; 
     } 
    } 

    // now print path. how to print it in fwd direction? 
    i=optimallastindex; 
    printf("%d ",array[i]); 
    while(parent[i]!= i) 
    { 
     printf("%d ",array[parent[i]]); 
     i=parent[i]; 

    } 

}

來源

2011-06-12 xyz

詢問如何使您的代碼正常工作，就像您希望它不在此處的主題一樣。我已經將此遷移到Stack Overflow。雖然如果您發佈完成的代碼以進行一般代碼審查，但一旦它達到您的要求，它會很好。 – sepp2k 2011-06-12 09:10:17

只需將反轉路徑存儲在臨時數組中，然後向後迭代該數組。

來源

2011-06-12 09:15:04 sepp2k

換句話說，你可以使用堆棧。 – 2011-06-12 09:19:55

好的，謝謝。我想知道如果沒有任何額外的空間，我可以做到這一點，但實際上並不需要。它不會改變空間複雜性。因爲對於大小爲O（n）的表格，打印路徑不會超過O（n）空間，並且對於任何空間O（n^2）表格，打印路徑不會比空間O（n^2）多得多，。所以，我認爲我們很好。謝謝。 – xyz 2011-06-12 10:19:51

只需將父項複製到新數組（或堆棧）中，然後按照反向順序迭代數組，或者不使用父項，而是在else語句中執行next[i-1] = i。

來源

2011-06-12 09:21:39

如何打印從動態編程技術開始的最佳路徑

回答

相關問題