动态规划 - 活动选择

我是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

动态规划 - 活动选择

回答

相关问题