作业调度贪心算法如何返回获取最大收益的选中项目集合？

要让你的动态规划算法返回最大收益对应的选中项目，只需修改递归函数，让它同时返回最大收益值和选中的项目列表，核心思路是在递归决策时记录选择路径。

修改后的代码实现 #

from dataclasses import dataclass
from datetime import date


@dataclass
class InvestmentProject:
    profit: int
    begin_date: date
    end_date: date

    def __repr__(self):
        # 自定义打印格式，方便查看项目信息
        return f"项目(收益={self.profit}, 开始={self.begin_date}, 结束={self.end_date})"


def get_max_sequence(arr, i=0):
    if i == len(arr):
        # 递归终止：没有项目可选，收益0，空列表
        return 0, []
    
    # 找到第一个不与当前项目冲突的后续项目索引j
    j = i + 1
    while j < len(arr) and arr[i].end_date > arr[j].begin_date:
        j += 1
    
    # 选择当前项目：收益为当前利润+后续j开始的最大收益，列表包含当前项目+后续选中的项目
    select_profit, select_list = get_max_sequence(arr, j)
    total_select_profit = arr[i].profit + select_profit
    total_select_list = [arr[i]] + select_list
    
    # 不选择当前项目：收益为i+1开始的最大收益，列表为后续选中的项目
    skip_profit, skip_list = get_max_sequence(arr, i+1)
    
    # 比较两种选择的收益，返回收益更高的组合
    if total_select_profit > skip_profit:
        return total_select_profit, total_select_list
    else:
        return skip_profit, skip_list


def main():
    arr = [
        InvestmentProject(30, date(2022, 10, 10), date(2022, 10, 14)),
        InvestmentProject(15, date(2022, 10, 15), date(2022, 10, 16)),
        InvestmentProject(25, date(2022, 10, 12), date(2022, 10, 15)),
        InvestmentProject(10, date(2022, 10, 20), date(2022, 10, 26)),
    ]
    # 注意：作业调度问题通常按结束日期排序能更高效找到冲突项目，这里保留原代码的开始日期排序逻辑
    sorted_arr = sorted(arr, key=lambda x: x.begin_date)
    max_profit, selected_projects = get_max_sequence(sorted_arr)
    print(f"最大收益：{max_profit}")
    print("选中的项目：")
    for proj in selected_projects:
        print(proj)


if __name__ == "__main__":
    main()

关键修改说明 #

• 递归函数返回值改为元组(收益值, 选中项目列表)，在每一层递归中记录选择路径
• 分别计算「选择当前项目」和「不选择当前项目」两种情况的收益与项目列表，最终返回收益更高的组合
• 给InvestmentProject添加了__repr__方法，方便打印项目的具体信息
• 主函数中拆分返回值，分别打印最大收益和选中的项目

额外优化提示 #

原代码按项目开始日期排序，作业调度问题中更高效的做法是按结束日期排序，这样可以用二分查找快速找到第一个不冲突的项目（替代原代码的while循环），提升算法效率，尤其是当项目数量较多时。

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