合作解谜中,不同角色可能只会处理部分机关。按角色顺序分配第一个可用机关很直观,却可能把唯一合适的位置占走。重新安排已有分工有时才能让更多人同时工作。

先固定规则和输入

六名角色与六个机关用零到五编号,每人最多负责一个机关,每个机关最多由一人负责。表内列出角色能够操作的机关,目标只求参与人数最多,不比较移动距离或完成速度。

角色0可操作[3, 5] 角色1可操作[0, 1, 2, 5] 角色2可操作[3, 5] 角色3可操作[1, 2] 角色4可操作[2, 3, 4] 角色5可操作[1, 3]

把结果按步骤记下来

纳入角色0,能力表[3, 5],允许调整此前分工后,当前[角色,机关]为[[0, 3]],共有1名角色获得位置。

纳入角色1,能力表[0, 1, 2, 5],允许调整此前分工后,当前[角色,机关]为[[0, 3], [1, 0]],共有2名角色获得位置。

纳入角色2,能力表[3, 5],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 0], [2, 3]],共有3名角色获得位置。

纳入角色3,能力表[1, 2],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 0], [2, 3], [3, 1]],共有4名角色获得位置。

纳入角色4,能力表[2, 3, 4],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 0], [2, 3], [3, 1], [4, 2]],共有5名角色获得位置。

纳入角色5,能力表[1, 3],允许调整此前分工后,当前[角色,机关]为[[0, 5], [1, 0], [2, 3], [3, 2], [4, 4], [5, 1]],共有6名角色获得位置。

贪心分配[[0, 3], [1, 0], [2, 5], [3, 1], [4, 2]]共5人,最终匹配[[0, 5], [1, 0], [2, 3], [3, 2], [4, 4], [5, 1]]共六人。六名角色构成参与人数上限,达到六即证明最优;本例不承诺最优分配只有一种。

自己复核的办法

先记录按编号贪心分配的结果,再寻找可以挪动旧分工的增广路线。用一组互不冲突的完整分配证明可行,并检查没有角色被分到能力表之外的机关。

建议先遮住结果,用本例原始输入独立完成一遍,再逐项对照。若出现差异,先找最早不一致的位置,检查索引从零还是从一开始、边界是否包含,以及比较或更新发生的先后。只比较最后一个数,往往无法分辨规则理解与计算步骤分别出了什么问题。

使用这个练习的边界

这是一对一能力匹配模型,不能直接代替有时间窗口、多人协作或互斥工具的排程。若一个机关需要两人同时操作,必须把额外约束明确写进模型,不能让同一角色被重复计算。