申し訳ありませんが、これはコードというよりも論理的なレイアウトになります...
配列(1,2,3,4)が最初の料理のスコアなのか、最初の料理のスコアなのかははっきりしませんが、おそらく次のような配列を使用します
$array[$cook_id][$dish_number] = $score;
$array[$cook_id] = array($lowest_scored_dish,...,$highest); となるように各配列を asort() します。
最高の料理と別の料理のスコアの差になるように、特定の料理人が料理を作るための重み付けされた好みを考えてみましょう。
非常に単純な例として、料理 a,b,c と料理 0,1,2
$array['a'] = array(0=>100, 1=>50, 2=>0); // cook a prefers 0 over 1 with weight 50, over 2 with weight 100
$array['b'] = array(0=>100, 1=>100, 2=>50); // cook b prefers 0,1 over 2 with weight 50
$array['c'] = array(0=>50, 1=>50, 2=>100); // cook c prefers 2 with weight 50
asort() の後: $array['a'] = array(0=>100, 1=>50, 2=>0); $array['b'] = array(0=>100, 1=>100, 2=>50); $array['c'] = array(2=>100, 0=>50, 1=>50);
料理 'a' から始めて、料理 0 を自分の次善の料理よりも 50 ポイント (重み) 好みます。Cook 'b' も dih 0 を好みますが、次の料理よりも重みが 0 です。したがって、可能性は高いです (ただし、「a」の料理人が料理を 0 にするかどうかはまだ定かではありません。
料理 0 を予約済みと見なし、「b」の調理に進みます。料理 0 を除いて、料理人 'b' は料理 1 を好みます。料理 1 を好む料理人は他にいないため、料理人 'b' には料理 1 が割り当てられます。
クック 'c' はデフォルトでディッシュ 2 を取得します。
これは、各料理人が個人的な最大のものを調理する非常に便利な例ですが、うまくいくいくつかのロジックの例であることを願っています.
不便にしましょう:
$array['a'] = array(0=>75, 1=>50, 2=>0);
$array['b'] = array(0=>100, 1=>50, 2=>50);
$array['c'] = array(0=>100, 1=>25, 2=>25);
料理 'a' で再度開始し、0 が優先されることを確認しますが、今回は重み 25 を使用します。料理 'b' は重み 50 を好み、料理 'c' は重み 75 を好みます。料理 'c' は料理 0 を獲得します。 .
利用可能な料理人のリストに戻ると、'a' は重み 50 の 1 を好みますが、'b' は重み 0 の料理を好みます。'a' は料理 1 を取得し、'b' は料理 2 を取得します。
これですべての複雑さが解消されるわけではありませんが、正しい方向への一歩です。最初の料理と料理の組み合わせに対する想定が間違っている場合があります。
あまり便利ではありません：
$array['a'] = array(0=>200, 1=>148, 2=>148, 3=>0);
$array['b'] = array(0=>200, 1=>149, 2=>0, 3=>0);
$array['c'] = array(0=>200, 1=>150, 2=>147, 3=>147);
$array['d'] = array(0=>69, 1=>18, 2=>16, 3=>15);
'a' は最大値であり、0 を好む他の誰もより高い重みを持たないため 0 を取得します 'b' は 1 を獲得し、149 の重みで 'd' を獲得しますc' は 3 を取得します
スコア: 200+149+147+16 = 512
すべての順列をチェックせずに収集した推測は適切ですが、間違っている可能性があります。ここから、「一人の料理人が別の料理人と交換したら、合計は増えますか?」と尋ねます。
答えはイエスです。a(0)+d(2) = 200+16 = 216 ですが、a(2)+d(0) = 148+69 = 217 です。
重み付けされたアプローチを使用して「最良の推測」のコードを書くことはあなたに任せますが、その後、ここから始めるのが良いでしょう:
// a totally uneducated guess...
$picks = array(0=>'a', 1=>'b', 2=>'c', 3=>'d');
do {
$best_change = false;
$best_change_weight = 0;
foreach ($picks as $dish1 => $cook1) {
foreach ($picks as $dish2 => $cook2) {
if (($array[$cook1][$dish1] + $array[$cook2][$dish2]) <
($array[$cook1][$dish2] + $array[$cook2][$dish1]))
{
$old_score = $array[$cook1][$dish1] + $array[$cook2][$dish2];
$new_score = $array[$cook1][$dish2] + $array[$cook2][$dish1];
if (($new_score - $old_score) > $best_change_weight) {
$best_change_weight = $new_score - $old_score;
$best_change = $dish2;
}
}
}
if ($best_change !== false) {
$cook2 = $picks[$best_change];
$picks[$dish1] = $cook2;
$picks[$dish2] = $cook1;
break;
}
}
} while ($best_change !== false);
これが機能しないことを示す反例は見つかりませんが、 ($array[$cook1][$dish1] + $array[$cook2][$dish2]) = = ($array[$cook1][$dish2] + $array[$cook2][$dish1])
たぶん、他の誰かがこの「もしも？」に対する答えをフォローアップするでしょう。
このマトリックスを考えると、括弧内の項目は「ピック」です
[a1] a2 a3
b1 [b2] b3
c1 c2 [c3]
a1 + b2 == a2 + b1 の場合、'a' と 'b' は料理を切り替えません。私が100％確信が持てない場合は、これがより良い選択であるようなマトリックスが存在するかどうかです：
a1 [a2] a3
b1 b2 [b3]
[c1] c2 c3
最初の状態から 2 番目の状態に移行するには 2 つのスイッチが必要です。最初の状態は合計を変更しないため、任意のように見えます。しかし、この恣意的な変更を経ることによってのみ、最後の切り替えを行うことができます。
上で書いた「重み付けされた好み」モデルに基づいて、最初のモデルが選択されるだけでなく、実際の最適な選択が 2 番目のモデルによって与えられるような 3x3 の例を見つけようとしました。例を見つけることができませんでしたが、それが存在しないという意味ではありません。今は行列代数をこれ以上やろうとは思わないが、おそらく誰かが私が中断したところから始めるだろう. 一体、そのケースは存在しないのかもしれませんが、懸念事項を指摘する必要があると思いました。
それが機能し、正しい選択で開始した場合、上記のコードは 8 つの料理/皿に対して 64 回 (8x8) ループします。ピックが正しくなく、最初のクックが変更された場合、最大 72 になります。8 番目のクックが変更された場合、最大 128 になります。do-while が数回ループする可能性がありますが、疑わしいと思います。 40k の組み合わせをすべて合計するのに必要な CPU サイクル近くまで上昇します。