基于贪心算法优化Tiny Tower游戏员工岗位分配的技术咨询

核心贪心逻辑 #

要最大化整体绩效，核心就是优先搞定最高价值的匹配：

• 所有员工-门店的组合里，技能分越高的越先处理，确保9分的匹配优先填满对应门店空缺，再处理8分及以下的
• 每个员工优先分配给自己技能分最高的门店，若该门店没位置了，再依次尝试次高技能分的门店

伪代码&实现步骤 #

1. 生成所有可能的员工-门店匹配条目 #

遍历每一位员工，为他生成对应5类门店的匹配数据，每条数据包含：

• 员工姓名
• 对应门店的技能分
• 门店的索引（对应store_types和k的下标，方便后续操作）

举个例子，员工lawson的技能数组是[6,2,9,9,2]，生成的条目就是：
('lawson', 6, 0), ('lawson', 2, 1), ('lawson', 9, 2), ('lawson', 9, 3), ('lawson', 2, 4)

2. 对匹配条目按技能分降序排序 #

把所有生成的条目从高到低排序，技能分相同的条目顺序不影响最终绩效。排序后，9分的条目会全部排在最前面，接下来是8分，以此类推。

3. 执行分配操作 #

先初始化几个变量：

• assigned：字典，键是门店索引，值是已分配到该门店的员工列表，用来存最终分配结果
• remaining_slots：复制原空缺数组k，用来实时跟踪各门店还剩多少空位
• used_workers：集合，用来记录已经被分配的员工，避免重复分配

然后遍历排序后的匹配条目：

total_workers = len(workers)
for each entry in sorted_matches:
    worker_name, skill_score, store_idx = entry
    if worker_name in used_workers:
        continue
    if remaining_slots[store_idx] > 0:
        # 把员工分配到该门店
        if store_idx not in assigned:
            assigned[store_idx] = []
        assigned[store_idx].append(worker_name)
        used_workers.add(worker_name)
        remaining_slots[store_idx] -= 1
    # 提前终止条件：所有空位都填满，或者所有员工都被分配
    if all(slot == 0 for slot in remaining_slots) or len(used_workers) == total_workers:
        break

4. 整理输出结果 #

把assigned里的门店索引对应到store_types的名称，转换成易读的格式，比如：

green门店：['washington', 'randy', ...]
blue门店：['lawson', ...]

特殊情况兼容 #

• 员工过剩：当所有门店空位都被填满后，剩下的员工不会被加入used_workers，循环自动跳过这些员工，算法正常终止
• 岗位空缺：当所有员工都被分配后，remaining_slots里的正数就是未填满的岗位，循环会提前终止，不会出现崩溃问题

内容的提问来源于stack exchange，提问作者mars