1

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

1 回答 1

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 并开始编写程序。

于 2013-03-22T09:31:11.870 回答