动态编程-活动选择

Question

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

Answer 1

我不是在实现你的伪代码，我只是向你展示它是如何在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并开始编写程序。