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

これまでGreedy Algorithmでできていたのですが、

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++ でどのようにできるかを示しているだけです。1 つの可能性は次のとおりです。

// ...
// 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 に答える