为忙碌贪心的泥瓦匠Kemo规划最高收入

"10347忙碌又贪心的泥瓦匠" 这是一个关于调度优化问题的编程题目，目标是帮助名叫Kemo的泥瓦匠安排他的工作计划，以最大化他在一定时间内赚取的总工钱。问题的核心在于确定哪些工作可以相互兼容，即不会在时间上产生冲突。题目描述了以下关键点： 1. **问题背景**：村里有一个泥瓦匠Kemo，他只能一次为一个雇主工作，并且必须连续完成工作，不能在多个任务之间交替。如果不能按照预约时间工作，他就无法得到报酬。 2. **输入信息**：包括预约工作的雇主数量（n）、每个雇主的起始工作时间、每个工程的持续天数以及每天的工钱。所有工作都能在第1000天内完成。 3. **输出目标**：计算出Kemo在完成一系列工作后能获得的最大总工钱。 4. **解题方法**：虽然题目标题中有“贪心”，但实际问题不适合使用贪心算法解决。正确的方法是采用**回溯算法**来搜索所有可能的工作组合。建立一个子集树，其中根节点代表空集合，叶节点代表所有可能的工作选择。在搜索过程中，遵循以下规则： - **相容性检查**：如果当前选择的工作与之前已选的工作在时间上不冲突（即起始时间和结束时间无交集），则继续向下搜索。 - **剪枝策略**：如果当前工作与已选工程集合不相容，则剪枝，返回上一层，不考虑该分支。 5. **样例输入和输出**：给出了一组具体的数据，展示了如何计算最大收益。在样例中，Kemo最多可以赚59元。 6. **提示**：题目提示不要被“贪心”误导，暗示了直接的贪心策略无法解决问题，需要全局考虑所有可能的工作组合。 解决这个问题的关键在于实现回溯算法，有效地检查和排除不相容的工作组合。这涉及到对所有可能子集的遍历，并在每个节点处进行相容性检查。最后，从所有相容的子集中找出使Kemo收入最大的那个组合。由于问题规模限制（n<=100），这种算法的效率是可接受的。在实际编程时，可以使用动态规划或贪心策略的变种来优化解决方案，但基本思路仍然是全搜索。