抱歉,但这将更像是逻辑布局而不是代码......
我不太清楚 array(1,2,3,4) 是第一道菜还是第一个厨师的分数,但我可能会使用这样的数组
$array[$cook_id][$dish_number] = $score;
asort() 每个数组,使得 $array[$cook_id] = array($lowest_scored_dish,...,$highest);
考虑一个特定厨师做一道菜的加权偏好是最好菜与另一道菜的得分之差。
作为一个非常简单的示例,烹饪 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。
Cook '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' 喜欢 1 的重量为 50,但 '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' 以 149 的权重赢得 1 'd' 赢得 2,因为 'c' 在可用选项中没有偏好' 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
从第一个状态到第二个状态需要两个开关,第一个似乎是任意的,因为它不会改变总数。但是,只有通过这种任意更改才能进行最后一次切换。
我试图找到一个 3x3 的例子,这样基于我上面写的“加权偏好”模型,第一个将被选择,但真正的最佳选择由第二个给出。我找不到一个例子,但这并不意味着它不存在。我现在不想做更多的矩阵代数,但也许有人会从我离开的地方继续。哎呀,也许这种情况不存在,但我想我应该指出这个问题。
如果它确实有效并且你从正确的选择开始,上面的代码将只循环 64 次 (8x8) 用于 8 个厨师/菜肴。如果选择不正确并且第一个厨师有变化,那么它将上升到 72。如果第 8 个厨师有变化,则上升到 128。do-while 可能会循环几次,但我怀疑它将接近对所有 40k 组合求和所需的 CPU 周期。