Ruby实现：将指定份数午餐的餐盒分配至特定容量烤箱的算法

核心目标 #

同时满足两个优先级：

1. 最少使用烤箱数量
2. 最大化已使用烤箱的容量填充率

算法步骤（结合示例数据） #

示例数据：

• 烤箱（容量）：烤箱1(25)、烤箱2(25)、烤箱3(10)
• 餐盒（份数）：餐盒1(3)、餐盒2(12)、餐盒3(2)、餐盒4(5)、餐盒5(20)、餐盒6(4)、餐盒7(5)

1. 预处理排序

• 烤箱按容量降序排列：[25, 25, 10]（优先用大容量烤箱，减少总使用数量）
• 餐盒按份数降序排列：[20, 12, 5, 5, 4, 3, 2]（先处理大分量餐盒，避免大餐盒占用额外烤箱）

2. 优先分配大分量餐盒

遍历排序后的餐盒，给每个餐盒找第一个剩余容量足够且未被完全占用的烤箱：

• 餐盒5(20)：放入烤箱2，烤箱2剩余容量=25-20=5
• 餐盒2(12)：放入烤箱1，烤箱1剩余容量=25-12=13

3. 贪心填充剩余空间

对每个已使用的烤箱，用剩余的小分量餐盒（仍按降序）填充剩余容量：

• 烤箱1剩余13：
  • 放入餐盒4(5)，剩余13-5=8
  • 放入餐盒7(5)，剩余8-5=3
  • 放入餐盒1(3)，剩余3-3=0（完全填满）
• 烤箱2剩余5：
  • 放入餐盒6(4)，剩余5-4=1（无更小的餐盒可填充）
• 剩余餐盒3(2)：放入最小的可用烤箱（烤箱3），剩余10-2=8

4. 最终分配结果

• 烤箱1：餐盒1、2、4、7 → 3+12+5+5=25/25（填满）
• 烤箱2：餐盒5、6 →20+4=24/25
• 烤箱3：餐盒3 →2/10

关键注意事项 #

• 贪心算法的局限性：该方法适合小规模数据，能快速得到近似最优解；如果是大规模、极端复杂的组合场景，可能需要回溯法或动态规划，但效率会显著降低
• 异常处理：如果存在单个餐盒容量超过所有烤箱最大容量的情况，需提前判定并提示无法分配
• 灵活性：相同容量的烤箱可灵活调整分配顺序，只要最终满足核心目标即可

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