1

私は自分の課題のトピックに関する多くの研究を見つけましたが、それは私が望むものに近いですが、正確ではありません. 多くの割り当てでは、文字列の順列を見つけることが強制されているようですが、これも同様のアプローチです。私は再帰の初心者なので、コードをトレースするのに苦労しています。別の投稿でこのスニペットを見つけました：

void swap(char* str, int i, int j)
{
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
}

void permute(char *string, int start, int end)
{
    if(start == end)
   {
        printf("%s\n", string);
        return;
    }

    permute(string, start + 1, end);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(string[start] == string[i])
            continue;
        swap(string, start, i);
        permute(string, start + 1, end);
        swap(string, start, i);
    }
}

そこから、文字列の長さが i のインデックスと同じ場合が基本ケースであることがわかります。ただし、私の課題では、少し異なることを行う必要があります。可能なカップルの間で「マッチメーカー」をするように求められます。男性と女性が同数与えられ、それぞれが「適合性」の尺度を持っています。私たちの目標は、このマッチング数を最大化することです。したがって、男性 3 人 * 女性 3 人 (常に完全な数のカップルになります) の場合、次のようになります。

 {[M1, W1], {[M1, W1], {[M1, W2],
  [M2, W2],  [M2, W3],  [M2, W1],
  [M3, W3]}  [M3, W2]}  [M3, W3]}
  ....
  // Match #(n)! or in this case 6 (3*2*1)

;

等々。結果として得られる順列の数は (n) になることがわかっています! ここで、n はカップルの数です。したがって、10 人の男性と 10 人の女性は (10) になります。ソリューション。これをすべて念頭に置いて、私が見つけたこのコードは私が探しているものと似ていますか、それとも変更する必要がありますか? これは、2 つの別々の配列を並べ替える場合でも、線形配列を並べ替えるため、変更する必要があると考えています。

皆さんはどう思いますか？

4

1 に答える 1

1

2つの別々の配列を並べ替える必要はありません。一方を並べ替えるだけで、もう一方は一定のままにしておく必要があります。これは、男性と女性に一致するすべての可能な解決策をチェックすることを保証するのに十分です。証明は簡単でMen、女性のインデックスにすぎません。女性の配列のすべての順列は、それらを順序付けるすべての方法を見つけています。つまり、女性のインデックスにすべての可能性を割り当てています。

3人の男性と3人の女性の簡単な例を見てみましょう。

data = [M1,M2,M3] [W1,W2,W3]
opt1: M1+W1, M2+W2, M3+W3
opt2: M1+W1, M2+W3, M3+W2
opt3: M1+W2, M2+W1, M3+W3
opt4: M1+W2, M2+W3, M3+W1
opt5: M1+W3, M2+W1, M3+W2
opt6: M1+W3, M2+W2, M3+W1

[W1,W2,W3]簡単なので、これらがすべての可能性であり、男性の配列がそのままである間、女性の配列（）のみを並べ替えました。

編集：
あなたがすでに持っているコードに基づいて、これができることです：

int permute(int men[], int women[], int start, int end)
{
    if(start == end)
   {
        int i =0, sum = 0;
        for (i = 0; i < end; i++) sum += score(men[i],women[i]);
        return sum;
    }
    best = -INFINITY;
    best = max(permute(men, women, start + 1, end), best);
    int i;
    for(i = start + 1; i < end; i++)
    {
        if(women[start] == women[i])
            continue;
        swap(string, start, i);
        best = max(permute(men, women, start + 1, end), best);
        swap(women, start, i);
    }
    return best;
}

上記は、を並べ替えるだけwomenであり、stop句でスコアをチェックし（intと仮定）、反復で見つかった「最高の」スコアを返します（ここで最高が最高であると仮定）。 また、各試合のスコアを見つける
関数があると仮定しましたint score(int,int)

注：これはcスタイルの擬似コードであり、テストされておらず、構文上の問題がある可能性があります。

于 2013-01-31T11:17:25.213 に答える