如何优化午餐盒分配问题的Python代码，提升效率与可读性？

原代码的核心问题 #

你当前的代码通过枚举所有可能的学校组合（借助combinations）寻找符合条件的最大分配数，存在两个致命缺陷：

1. 时间效率极低：枚举所有组合的时间复杂度为O(2^m)，当学校数量m超过20时，组合数会突破百万级，运行速度急剧下降。
2. 内存浪费严重：将所有符合条件的组合存入Result_List，当m较大时会占用大量内存空间。

最优优化思路：贪心算法 #

要最大化分配的学校数量，最直接的策略是优先给需求午餐盒最少的学校分配——用最少的资源覆盖最多的对象，才能在总数量限制下拿到最大的学校数。

具体步骤：

• 将所有学校的午餐盒需求从小到大排序
• 从最小的需求开始累加，直到加上下一个需求会超过总午餐盒数量为止，此时累加的次数就是最多能分配的学校数

优化后的代码 #

# 读取总午餐盒数与学校数量
total_lunchboxes, school_count = map(int, input().split())

# 读取各学校需求并排序
school_demands = []
for _ in range(school_count):
    school_demands.append(int(input()))
school_demands.sort()

# 计算最多可分配的学校数
current_total = 0
max_school_num = 0

for demand in school_demands:
    if current_total + demand <= total_lunchboxes:
        current_total += demand
        max_school_num += 1
    else:
        break

print(max_school_num)

代码说明 #

• 排序处理：把需求从小到大排序，确保优先处理最"省"资源的学校，最大化覆盖数量
• 累加判断：逐个累加需求，一旦超过总数量就停止，此时统计的学校数即为最大值
• 效率对比：排序的时间复杂度为O(m log m)，后续遍历为O(m)，整体效率远高于原代码的指数级复杂度，且几乎不占用额外内存

用示例输入测试：需求[3,9,4,2]排序后为[2,3,4,9]，累加过程为2→5→9，均未超过10，最终得到可分配3所学校，与示例结果一致。

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