動態規劃 - 活動選擇

我是C++新手。有人可以將此算法轉換爲C++代碼。我無法完全理解它，謝謝。動態規劃 - 活動選擇

我能夠使用表格矩陣解決紙面上的問題，並且我理解它的分治策略，但是在將s和f數組傳遞給DP函數後難以實現算法。

for i =1 to n 
do m[i] = max(m[i-1], 1+ m [BINARY-SEARCH(f, s[i])]) 
      We have P(i] = 1 if activity i is in optimal selection, and P[i] = 0 
      otherwise 
      i = n 
      while i > 0 
       do if m[i] = m[i-1] 
         then P[i] = 0 
            i = i - 1 
         else 
            i = BINARY-SEARCH (f, s[i]) 
            P[i] = 1

到目前爲止，我已經能夠用貪心算法來做到這一點，

void MaxActGreedy(int s[], int f[], int n) 
{ 
cout<<"\n Entering Greedy Programming Function \n"; 
clock_t startTime = clock(); 

cout<<" Greedy Solution (Index no.) :"; 
int i; 
int j; 

i=0; 
cout<<i; 

for(j=1; j<n; j++) 
{ 
    if (s[j]>=f[i]) 
    { 
     cout<<j; 
    i=j; 
    } 
} 

clock_t endTime= clock(); 

endTime = endTime - startTime; 
float timeinSeconds = endTime/(float) CLOCKS_PER_SEC; 

cout<<"\n Greedy Time: "; 
cout<<timeinSeconds; 
cout<<" Seconds"; 

} 

void Dynamic(int s[],int f[],int n) 
{ 
int m[]={0}; 

for(int i=0; i<n; i++) 
{ 



} 
} 

int main() 
{ 
int s[]={1,3,0,5,3,5,6,8,8,2,12};//Start Time Si 
int f[]={4,5,6,7,8,9,10,11,12,13,14};//Finish Times fi (sorted) 


int n = sizeof(s)/sizeof(s[0]); 

MaxActGreedy(s,f,n); 
// MaxActDP(s,f,n); 
Dynamic(s,f,n); 



return 0; 
}

來源

2013-03-22 Najam Qureshi

瞭解算法的作用，然後用_any_語言實現它會簡單得多。 – 2013-03-22 09:13:07

「但實施困難..」顯示你的困難。 – qPCR4vir 2013-03-22 09:29:14

@ qPCR4vir我在我的問題中添加了代碼。 – 2013-03-22 09:32:01

我沒有實現你的僞代碼，我只是顯示你怎麼能在C++中。一種可能性是：

// ... 
// Declarations, prototypes, header file inclusions, ... 
// ... 
for (int i=1; i<=n; i++) 
{ 
    m[i] = max(m[i-1], 1+ binarySearch(f, s[i])); 

    if (activity_is_in_optimal_selection(i)) 
     P[i] = 1; 
    else 
     P[i] = 0; 

    i = n; 

    while (i>0) 
    { 
     if (m[i]==m[i-1]) 
     { 
      P[i] = 0; 
      i--; 
     } 
     else 
     { 
      i = binarySearch(f, s[i]); 
      P[i] = 1; 
     } 
    } 
}

我不知道，我明白你的算法或沒有，但打開你的IDE並開始編寫程序。

來源

2013-03-22 09:31:11 Raymond

動態規劃 - 活動選擇

回答

相關問題