算法设计与分析贪心算法习题

### 关于贪心算法的习题和练习材料

#### 一、理论基础
贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致全局结果最优的算法[^1]。

#### 二、具体实例解析

##### 会议调度问题
在一个会议室里有多个活动申请使用该房间，每个活动有一个开始时间和结束时间。假设同一时刻只能举行一个活动，请问如何安排这些活动才能使尽可能多的活动顺利举办？

这个问题可以通过按结束时间升序排列所有活动来求解；当存在两个以上具有相同最早结束时间的任务时，则优先考虑其中最先开始的那个任务。这种做法能保证每次选取最短时间段内的事件，进而留出更多空间给后续可能发生的其他事情[^3]。

def activity_selection(start, finish):
    n = len(finish)
    i = 0
    print(i,end=" ")
    
    for j in range(n):  
        if start[j] >= finish[i]:
            print(j,end=" ") 
            i = j
            
start = [1 , 3 , 0 , 5 , 8 , 5]
finish = [2 , 4 , 6 , 7 , 9 , 9]

activity_selection(start, finish)

上述代码实现了简单的活动选择函数，它接收两个列表作为参数：一个是各个活动中最早的启动时间节点组成的数组`start[]`;另一个是由对应截止期限构成的数据集合`finish[]`. 函数内部先初始化索引变量i=0表示第一个被选中的项目位置;接着遍历整个序列，在满足条件的情况下输出符合条件项目的下标并更新指针指向最新加入方案集里的成员.

#### 三、更复杂的案例研究

考虑到某些情况下除了关注完成数量外还需要兼顾成本因素的影响，比如下面这个变种版本：

假设有若干项工作等待处理，每件都有各自的报酬金额以及所需消耗的工作小时数。现在要求合理分配有限的人力资源使得最终获得最大收益的同时不超过规定工时总数T。此时可以借鉴背包问题的思想计算单位时间内创造价值最高的那部分作业组合起来形成整体解决方案.

from typing import List,Tuple

class Job:
    def __init__(self,value:int,time_cost:int)->None:
        self.value=value
        self.time=time_cost
        
jobs=[Job(10,2),Job(5,3)] # 假设只有两项工作任务可供挑选...
max_time=4                 # ...并且可用的最大时间为四个钟头.
dp=[[0]*(max_time+1)for _ in range(len(jobs)+1)]

for idx in reversed(range(len(dp)-1)):
    job=jobs[idx]
    for t in reversed(range(max_time+1)):
        dp[idx][t]=dp[idx+1][t]
        if(job.time<=t and (job.value+dp[idx+1][t-job.time])>dp[idx][t]):
            dp[idx][t]=(job.value+dp[idx+1][t-job.time])

print("Maximum profit:",dp[0][-1])

此段程序定义了一个名为`Job`类用于存储单个工作对象的信息（即赚取的钱财数目及其占用的时间长度），并通过二维表`dp[][]`保存不同状态下的最佳效益数值以便递推得到最后的结果。