抱歉,这将更多地是逻辑布局而不是代码...
我不太清楚数组(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)
$array['b'] = array(0=>100, 1=>100, 2=>50)
$array['c'] = array(0=>50, 1=>50, 2=>100)
在使用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分。而厨师'b'也喜欢菜品0,但权重为0分。因此,目前看来厨师'a'应该做菜品0,但还不确定。
现在我们将菜品0视为已经被预定,然后考虑厨师'b'。除了菜品0外,厨师'b'最喜欢的是菜品1。由于没有其他厨师喜欢菜品1,所以菜品1被分配给了厨师'b'。
由于默认情况下,厨师'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)
从'cook a'开始重新尝试,发现0被优先选择,但这次权重为25。'cook b'偏爱权重为50的菜肴,而'cook c'则更喜欢权重为75的菜肴。'cook c' 赢得了第一道菜肴。
回到可用厨师列表,'cook a' 偏爱权重为50的第二道菜肴,但是'cook b' 偏好权重为0。'cook a' 得到了第二道菜肴,'cook b'得到了第三道菜肴。
这仍然无法解决所有复杂性,但是这是朝着正确方向迈出的一步。有时为第一个cook和dish组合所做的假设是错误的。
WAY不那么方便:
$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的权重获胜。
'd'以2的权重获胜,因为'c'在可用选项中没有偏好。
'c'得到了3分。
总分:200+149+147+16 = 512。
虽然这是一个不错的猜测,但它可能是错误的。从这里开始,问一下:“如果一个厨师与任何另一个厨师交换,总分会增加吗?”
答案是肯定的,a(0)+d(2) = 200+16 = 216,但是a(2)+d(0) = 148+69 = 217。
我将让你编写使用加权方法的“最佳猜测”的代码,但在此之后,这是一个很好的开始:
$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])。也许其他人会回答这个“What if?”
给出以下矩阵,其中方括号中的项是“选择”:
[a1] a2 a3
b1 [b2] b3
c1 c2 [c3]
如果a1 + b2 == a2 + b1,则“a”和“b”不会交换菜品。我不确定的情况是是否存在一个矩阵,使这是更好的选择:
a1 [a2] a3
b1 b2 [b3]
[c1] c2 c3
从第一个状态到第二个状态需要两个开关,第一个开关似乎是任意的,因为它不会改变总数。但是,只有通过这个任意的改变才能进行最后一个开关。
我试图找到一个3x3的例子,使得基于上述“加权偏好”模型,第一个会被选择,但实际上最佳选择是第二个。我没有找到这样的例子,但这并不意味着不存在这样的情况。我现在不想再做更多的矩阵代数,但也许有人会接替我的工作。说不定这种情况不存在,但我认为我应该指出这个问题。
如果起始选择正确,则上述代码仅循环64次(8×8),适用于8个厨师/菜品。如果选择不正确并且第一个厨师有所更改,则循环次数将增加到72次。如果第8个厨师有所更改,则会增加到128次。可能会对do-while循环多次,但我怀疑它不会接近于求和所有40k组合所需的CPU周期。