Python程序贪婪算法求活动安排问题

### 贪婪算法解决考场调度问题 考场调度问题是典型的资源分配优化问题之一。通过应用贪婪策略，可以有效地减少冲突并最大化利用教室资源。 #### 解决方案概述 为了简化问题模型，假设存在一组考试课程以及有限数量的可用时间段和教室。目标是在满足所有约束条件的前提下安排尽可能多的考试。具体来说： - 每门课有固定的持续时间 - 不同科目之间可能存在重叠的学生群体 - 教室容量固定且不同大小 - 同一时段内同一间教室内只能举行一门考试 采用贪心法的核心思路是从尚未被安排的所有待考课程中挑选最合适的下一个要安插进去的那一项[^1]。 #### 实现方法 下面是一个简单的Python实现例子来展示如何基于上述原则构建一个基本版的考场调度程序: ```python from dataclasses import dataclass, field from typing import List @dataclass(order=True) class Exam: id: int duration: int students_count: int @dataclass class Classroom: capacity:int schedule:list=field(default_factory=list) def greedy_exam_scheduler(exams:List[Exam], classrooms:List[Classroom]): # 对考试按照参与人数降序排列 exams.sort(reverse=True) for exam in exams: assigned=False # 尝试将当前考试放入第一个能容纳它的空闲时段里 for classroom in classrooms: if sum([e.duration for e in classroom.schedule])+exam.duration<=classroom.capacity and not any((set(e.students)&set(exam.students))for e in classroom.schedule): classroom.schedule.append(exam) assigned=True break if not assigned: print(f'无法为考试 {exam.id} 找到合适的时间') exams=[Exam(id=i,duration=d,students_count=s) for i,(d,s) in enumerate(zip([90]*5,[30,40,20,50,60]))] classrooms=[Classroom(capacity=c) for c in [180,270]] greedy_exam_scheduler(exams,classrooms) print([(c.capacity,len(c.schedule),[(e.id,e.duration) for e in c.schedule]) for c in classrooms]) ``` 此代码片段定义了一个`Exam`类表示每场考试的信息；另一个`Classroom`类用于记录各个教室的状态及其已预约情况。函数`greedy_exam_scheduler()`接收两个列表参数——分别是待排定的日程表项目集合与可选场地清单，并尝试依据预先设定好的规则逐一处理每一项日程请求直到全部完成为止[^1]。

在Python中编写带有多个约束条件的贪心算法通常涉及选择每一步决策时，都尽可能地优化当前局部最优解，同时保证满足所有约束条件。贪心算法并不一定能找到全局最优解，但在许多复杂问题中能找到近似最优解。 下面是一个简单的示例，假设我们要创建一个求解0-1背包问题的贪婪算法，其中有两个约束条件：物品的数量不超过背包容量，以及总价值不超过给定的最大价值： ```python def greedy_knapsack(items, capacity): items.sort(key=lambda x: (x['value'] / x['weight'], -x['weight'])) # 按价值/重量降序，如果值相等则按重量升序排序 total_value = 0 total_weight = 0 for item in items: if total_weight + item['weight'] <= capacity and total_value + item['value'] <= max_value: # 约束条件检查 total_weight += item['weight'] total_value += item['value'] else: break # 如果超过背包容量，则停止添加 return total_value # 示例数据 items = [ {'name': 'item1', 'weight': 5, 'value': 10}, {'name': 'item2', 'weight': 4, 'value': 6}, {'name': 'item3', 'weight': 7, 'value': 8}, ] capacity = 10 max_value = 15 result = greedy_knapsack(items, capacity) print(f"最大价值: {result}")